📖 문제
문제 설명
일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.
- 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
- 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.
여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.
당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.
일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- a의 길이는 1 이상 1,000,000 이하입니다.
a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.- a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
- a의 모든 수는 서로 다릅니다.
입출력 예
| a | result |
|---|---|
[9,-1,-5] |
3 |
[-16,27,65,-2,58,-92,-71,-68,-61,-33] |
6 |
입출력 예 설명
입출력 예 #1
- 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.[9, -5]에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
- 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.[-1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
- 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.[-1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
- 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.
입출력 예 #2
- 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.
🧮 풀이
🧐 접근 방법
처음에 문제가 잘 이해되지 않아 접근법을 여기저기서 찾아보았지만 이해되는 풀이를 찾지 못해 제 기준 이해가 가장 잘 된 접근법을 공유하려 합니다.
이 문제의 핵심 규칙은 다음과 같습니다.
좌우 중 한 쪽에 자신보다 작은 풍선이 없다면 끝까지 살아남을 수 있다.
다시 말해, 좌우 양쪽에 자신보다 작은 풍선이 있다면 끝까지 살아남을 수 없다.
이것이 무슨 의미일까요?
먼저 풍선이 살아남을 수 없는 경우를 살펴봅시다. 문제의 조건에 따르면 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있기 때문에, 왼쪽에도 자신보다 작은 풍선이 있고 오른쪽에도 자신보다 작은 풍선이 있는 경우 풍선은 반드시 터지게 됩니다.
-2번 풍선 기준 예시입니다.
- 왼쪽의 인접한 두 풍선 -16번과 27번 중 큰 수인 27번 풍선을 터트리고, -16번 풍선이 남습니다.
- -16과 -92 모두 -2보다 작은 수이므로 더 작은 풍선을 터트리는 기회를 사용해야 합니다.
- -16번 풍선을 터트린다면, 남은 -2번과 -92번 풍선 중 더 큰 수인 -2번 풍선을 터트려야 합니다.
- -92번 풍선을 터트린다면, 남은 -16번과 -2번 풍선 중 더 큰 수인 -2번 풍선을 터트려야 합니다.
그럼 어떻게 해야 풍선이 살아남을 수 있을까요? 왼쪽이나 오른쪽 중 한 쪽에 자신보다 작은 풍선이 없어야 살아남을 수 있습니다.
-71번 풍선 기준 예시입니다.
- 오른쪽의 -71보다 큰 -68번과 -33번 풍선을 모두 터트립니다.
- 남은 -92번과 -71번 중에서 더 작은 풍선을 터트리는 기회를 사용하여 -92번 풍선을 터트리면 -71번 풍선을 남길 수 있습니다.
즉, 배열 a에 있는 어떤 풍선 a[i]을 기준으로 왼쪽에 있는 풍선들 중 최솟값, 오른쪽에 있는 풍선들 중 최솟값을 확인해서 왼쪽에도 a[i]보다 작은 풍선이 있고 오른쪽에도 a[i]보다 작은 풍선이 있는 경우를 제외하면 되는 것입니다.
따라서 다음과 같이 풀이를 진행할 수 있습니다.
1️⃣ 왼쪽에 작은 풍선이 있는지 확인
left 배열을 생성하고, i번째 풍선을 포함하여 왼쪽에 있는 풍선들 중 가장 작은 풍선을 기록합니다. i번째 풍선 왼쪽에 left[i]보다 작은 풍선은 없으므로, left[i]에 기록된 값은 끝까지 살아남을 수 있는 풍선임을 의미합니다.
let left = Array(len);
left[0] = a[0];
for (let i = 1; i < len; i++) {
left[i] = Math.min(left[i - 1], a[i]);
}2️⃣ 오른쪽에 작은 풍선이 있는지 확인
마찬가지로 right 배열을 생성하고, i번째 풍선을 포함하여 오른쪽에 있는 풍선들 중 가장 작은 풍선을 기록합니다. i번째 풍선 오른쪽에 right[i]보다 작은 풍선은 없으므로, right[i]에 기록된 값은 끝까지 살아남을 수 있는 풍선임을 의미합니다.
let right = Array(len);
right[len - 1] = a[len - 1];
for (let i = len - 2; i >= 0; i--) {
right[i] = Math.min(right[i + 1], a[i]);
}3️⃣ 살아남을 수 있는 풍선 계산
따라서
- 왼쪽에 자신보다 더 작은 풍선이 없는 풍선
- 오른쪽에 자신보다 더 작은 풍선이 없는 풍선
이 두 가지 조건 중 하나만 만족하면 살아남을 수 있는 풍선이 되므로, 이 두 집합의 중복을 제거한 합집합을 계산하기 위해 집합 자료형 Set을 이용하여 살아남을 수 있는 풍선의 수를 계산할 수 있습니다.
new Set([...left, ...right]).size;🌕 전체 코드
전체 코드는 다음과 같습니다.
function solution(a) {
let len = a.length;
let left = Array(len);
let right = Array(len);
left[0] = a[0];
for (let i = 1; i < len; i++) {
left[i] = Math.min(left[i - 1], a[i]);
}
right[len - 1] = a[len - 1];
for (let i = len - 2; i >= 0; i--) {
right[i] = Math.min(right[i + 1], a[i]);
}
return new Set([...left, ...right]).size;
}🧪 실행결과
left 배열 계산에 , right 배열 계산에 ,Set 생성에 의 시간 복잡도를 가지므로 최종적으로 의 시간 복잡도를 가져 문제 없이 통과할 수 있게 됩니다.
