문제
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
인접한 두 풍선을 터트릴 수 있는데, 남길 수 있는 풍선의 수를 구하는 문제이다.
이 문제의 키포인트는 인접한 풍선중에 작은 풍선을 한번만 터트린다는 것이다.
터지는 풍선의 조건을 어떻게 될까?
어떤 임의의 위치에서 풍선에서 왼쪽, 오른쪽의 최솟값보다 크다는 것은 터지는 풍선이라는 의미이다.
만약에 왼쪽 오른쪽 끝에서부터 번갈아가면서 큰 풍선들을 터트렸다고 치자.
그러면 제일 왼쪽, 오른쪽에서 제일 작은 풍선 두개가 남을 것이다. 그러면 나머지 풍선들은 다 터졌다.
결국 현재 위치를 기준으로 왼쪽, 오른쪽 최솟값보다 크다는 것은 터지는 풍선이다. 나머지는 남길 수 있는 풍선이라는 의미이다.
그리고 왜 answer=2부터 시작을 하는가?에 대해서 의문점을 가질 수 있다.
만약에 왼쪽 끝에 있는 풍선이라면, 나머지를 모두 터트렸다고 해도 작은 풍선도 한번은 터트릴 수 있기 때문에, 무조건 양 옆에 풍선은 남길 수 있다.
1. 오른쪽 왼쪽에 대한 최솟값의 변수를 선언하고 최솟값을 담을 배열을 선언한다.
2. 현재 위치에서 오른쪽, 왼쪽 최솟값을 갱신하고 위치에 최솟값을 담는다.
3. 현재 위치에서 오른쪽, 왼쪽 최솟값보다 크다는 의미는 터트려지는 풍선이라는 의미이므로 나머지를 센다.
소스코드
class Solution {
public int solution(int[] a) {
int leftMin = Integer.MAX_VALUE;
int rightMin = Integer.MAX_VALUE;
int length = a.length;
if (length == 1) {
return 1;
}
int[] left = new int[length];
int[] right = new int[length];
for (int i = 0; i < length; i++) {
if (leftMin > a[i]) {
leftMin = a[i];
}
left[i] = leftMin;
}
for (int i = length - 1; i >= 0; i--) {
if (rightMin > a[i]) {
rightMin = a[i];
}
right[i] = rightMin;
}
int answer = 2;
for (int i = 1; i < length - 1; i++) {
if (left[i] < a[i] && right[i] < a[i]) {
continue;
}
answer++;
}
return answer;
}
}
실행결과

'Problem Solving > Programmers' 카테고리의 다른 글
| [Programmers] 신고 결과 받기 - Java (0) | 2025.08.14 |
|---|---|
| [Programmers] 입국심사 - Java (0) | 2025.08.13 |
| [Programmers] 음양 더하기 - Java (0) | 2025.08.11 |
| [Programmers] 나누어 떨어지는 숫자 배열 - Java (2) | 2025.08.10 |
| [Programmers] 나머지가 1이 되는 수 찾기 - Java (0) | 2025.08.09 |