문제 정보
- 프로그래머스 Lv.3
- 탐색
- 문제 링크
풀이
이하의 규칙대로 개의 풍선을 1개만 남을 때까지 터트리는 걸 반복한 끝에, 마지막까지 남길 수 있는 풍선들의 개수를 구하는 문제다.
- 임의의 인접한 두 풍선을 고른 뒤, 둘 중 하나를 터트림
- 빈 공간이 생겼다면, 빈 공간이 없도록 중앙으로 밀착
- 인접한 두 풍선 중 번호가 더 작은 풍선을 터트리는 건 1번만 가능
3번 규칙처럼, 번호가 더 작은 풍선을 터트리는 건 1번만 가능하다. 즉 이 기회를 쓰지 않으면 전체 최소값은 무조건 마지막까지 남는다. 반대로, 이 기회를 쓴다면 최소값이 아닌 풍선도 남길 수 있다.
또한, 첫 번째와 마지막 풍선은 항상 남길 수 있다.
a[0]을 남기는 경우를 생각해보자. a[0]를 제외한 배열에서 하나가 남을 때까지 터트린다. 그 결과 남은 풍선이 a[k]라고 하면:
a[0]가 더 작으면, 그냥 큰 값인a[k]를 터트리면 된다.a[0]가 더 크면, 작은 걸 터트리는 기회를 사용하면 된다.
이는 a[n-1](마지막 풍선)에 대해서도 마찬가지다.
가운데 풍선 a[i] (0 < i < n - 1)가 남으려면 a[i] 기준 왼쪽 풍선들(a[0] ~ a[i - 1])과 오른쪽 풍선들(a[i + 1] ~ a[n - 1])을 모두 터트려야 한다. 더 작은 걸 터트리는 기회는 한 번 뿐이므로 왼쪽 또는 오른쪽 중 한 쪽에만 쓸 수 있다.
- 기회 없이 왼쪽을 모두 터트리려면: 왼쪽에서
a[i]보다 작은 값이 없어야 한다. 즉왼쪽 풍선들 중 최소값 > a[i] - 기회 없이 오른쪽을 모두 터트리려면: 오른쪽에서
a[i]보다 작은 값이 없어야 한다. 즉오른쪽 풍선들 중 최소값 > a[i]
둘 중 하나라도 만족하면 a[i]를 남길 수 있다.
즉, a[i] (0 < i < n - 1)에 대해서, 왼쪽 풍선들 중 최소값과 오른쪽 풍선들 중 최소값 중 하나라도 a[i]보다 크면, a[i]를 남길 수 있다.
매번 최소값을 탐색할 경우 이 되므로 각 인덱스 기준 왼쪽/오른쪽 최소값을 저장하는 배열 int[] leftMin, rightMin을 만들어 사용한다. 두 방향으로 각각 순회해 에 각 인덱스 기준 왼쪽/오른쪽 최소값을 미리 구해놓는 방식이다.
코드
class Solution {
public int solution(int[] a) {
int answer = 0;
int[] leftMin = new int[a.length];
int[] rightMin = new int[a.length];
leftMin[0] = Integer.MAX_VALUE;
rightMin[a.length - 1] = Integer.MAX_VALUE;
int i = 1;
int j = a.length - 2;
while (i < a.length && j > 0) {
leftMin[i] = Math.min(leftMin[i - 1], a[i - 1]);
rightMin[j] = Math.min(rightMin[j + 1], a[j + 1]);
i++;
j--;
}
for (int k = 0; k < a.length; k++)
if (leftMin[k] > a[k] || rightMin[k] > a[k])
answer++;
return answer;
}
}