풍선 터뜨리기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68646

문제 설명

일렬로 나열된 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의 모든 수는 서로 다릅니다.

접근

너무 큰 배열

배열의 길이가 1,000,000로 아주 커서 BFS나 DFS를 사용하면 시간 제한은 물론 재귀의 한계에 도달하거나 큐의 크기가 너무 커져 공간이 부족할 것이라고 생각했다. 따라서 완전 탐색은 시작부터 포기하고 DP에 이용할 수 있는 규칙이 있는지 찾아봤다.

한 번뿐인 기회

인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다.

이 문장에 집중해서 답이 될 수 있는 후보를 고민해봤다.
이 기회를 사용하지 않는다면 결국 이 배열 안에서 가장 작은 숫자만이 남을 것이다. 그렇다면 최솟값이 아닌 다른 숫자를 남기기 위해서는 이 최솟값과 만났을 때 이 기회를 사용해야 한다. 그렇다면 최솟값과 단 둘이 남기 위한 조건은 무엇인가?

결론

최솟값의 양 옆의 숫자는 언제든지 규칙에 따라 제거할 수 있다. 따라서 모든 풍선들은 최솟값의 옆에 오도록 풍선을 터뜨릴 수 있다. 따라서 어떤 풍선이 최솟값과 단 둘이 남기 위해서는 최솟값을 기준으로 반대편의 풍선을 모두 터뜨릴 수 있는지 확인하면 된다.

• 남길 풍선을 기준으로최솟값이 왼쪽에 있고 자신의 오른쪽에 자신보다 더 작은 수가 없는 경우
• 남길 풍선을 기준으로최솟값이 오른쪽에 있고 자신의 왼쪽에 자신보다 더 작은 수가 없는 경우

위에 해당하는 풍선의 개수를 구하면 답을 찾을 수 있었다.

예시

[-16,27,65,-2,58,-92,-71,-68,-61,-33]
다음과 같은 배열이 주어졌을 때, 최솟값은 -92이다.
-16은 마지막에 남는 것이 가능하다. -16과 -92 사이에 있는 숫자는 모두 -92와 비교하여 터뜨릴 수 있다. -92 오른쪽에 있는 숫자 또한 마찬가지다.

하지만 -2는 불가능하다. 27 65와 비교해서 터뜨리는 것이 가능하지만 -16을 터뜨릴 방법이 없다.

구현

첫 시도

처음에는 2중 for문을 사용해서 확인했다.

let answer = 1;
let min = Infinity;
let min_index = -1;
for (let i = 0; i < a.length; i ++) {
  if (min < a[i]) continue;
  min = a[i];
  min_index = i;
}
for (let i = 0; i < min_index; i++) {
  let result = 1;
  for(let j = 0; j < i; j++) {
    if (a[i] > a[j]) {
      result = 0;
      break;
    }
  }
  answer += result;
}
//이하 생략

하지만 이 방법은 $O(n^2)$의 시간 복잡도를 가지기 때문에 여전히 느렸다.

개선

약간의 생각 후, 양 끝에서 최솟값으로 순회하는 동안 최솟값을 갱신한다면 그것이 바로 자신보다 작은 숫자가 반대편의 없는 경우라는 것에 도달했다.

최종 코드

function solution(a) {
  	// 최솟값의 위치 탐색.
    let min = Infinity;
    let min_index = -1;
    for (let i = 0; i < a.length; i ++) {
        if (min < a[i]) continue;
        min = a[i];
        min_index = i;
    }
  	// 정답에 최솟값을 포함하고 시작.
    let answer = 1; 
  
  	// 만약 최솟값을 갱신한다면 마지막에 남을 수 있는 풍선.
  	// 왼쪽에서 최솟값 위치까지 순회
    let temp_min = Infinity;
    for (let i = 0; i < min_index; i ++) {
        if (temp_min > a[i]) {
            temp_min = a[i];
            answer ++;
        }
    }
  	// 오른쪽에서 최솟값 위치까지 순회
    temp_min = Infinity;
    for (let i = a.length - 1; i > min_index; i --) {
        if (temp_min > a[i]) {
            temp_min = a[i];
            answer ++;
        }
    }
    return answer;
}

$O(n)$의 시간 복잡도를 가지는 코드로 통과할 수 있었다.

후기

어떤 알고리즘을 알고 있느냐 보다는 시간 복잡도에 대해서 이해하고 어떤 방향으로 문제를 해결해야 하는지 방향을 잡는 것이 중요한 문제라고 생각한다. 제한 사항을 통해 완전 탐색이라는 선택지를 제외했고, 운좋게 규칙을 빠르게 찾아 시간이 오래 걸리지는 않았다.