[프로그래머스] LV.3 풍선 터트리기 (JS)

문제

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 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

풀이

다른 레벨3 문제들에 비해 난이도가 조금 있는 것 같다. 아무래도 월간 코드 챌린지 문제들이 기본적으로 제공되는 프로그래머스의 연습문제들 보다 평균 이상의 난이도를 가지는 것 같다. 해당 문제를 어떻게 접근하냐에 따라 굉장히 애를 먹을 수 있는 문제이다.

먼저 문제 조건에 의해 다음이 성립함을 알 수 있다.

• 풍선을 하나씩 터뜨려가다가 자기보다 작은 값을 2번 이상 마주치는 경우, 해당 풍선은 보존 불가

위의 규칙을 찾아내어 신나게 각 풍선끼리 일일이 비교하는 식으로 구현한다면 시간복잡도는 O(N^2)가 될 것이고, a의 최대 길이가 100만이기 때문에 당연히 시간 초과가 발생한다.

보통 O(N^2)에서 시간 초과가 발생하면 시간 복잡도를 최소 O(NlogN) 또는 O(N)까지 줄여할 필요가 있다. 물론 가지치기로 엄청난 최적화를 해낸다면 O(N^2)도 통과할 수도 있으니 항상 풀이가 한 가지만 존재하지 않는 까닭이겠다.

각설하고 쉽게 말해 반복문을 한 번만 돌려서는 해결할 수 없을지 찬찬히 생각해보자. 먼저 앞서 언급한 자신보다 작은 값을 2번 이상 마주치는 경우를 좀 더 딥하게 생각해보자.

위의 조건을 조금 바꾸어 표현한다면, 가장 작은 값과 두 번째로 작은 값은 항상 생존가능하다고 볼 수 있다. 가장 작은 값은 자신보다 작은 수가 없으니 모든 풍선을 제거할 수 있고, 두 번째로 작은 값은 자기보다 작은 값이 단 하나밖에 없으니 1번의 기회를 사용해 최후까지 생존할 수 있기 때문이다. 따라서 이 두개의 값은 어느 위치에 있든간에 항상 최후까지 남을 수 있다는 것이 보장된다.

그렇다면 다른 풍선들은 어떨까? 다른 풍선들의 경우는 어디에 위치하느냐에 따라 보존이 가능할 수도, 또는 보존이 불가능할 수도 있다. 예를 들어 가장 작은 값이 M1 이고 두 번째로 작은 값이 M2 라고 할 때, 지금 제거하려는 풍선을 cur 이라고 해보자. 이때 cur가 마주치는 상황은 아래와 같다.

1. M1 ... cur ... M2 사이에 위치한다면 보존이 불가능하다. 최후에 남는 값은 [M1, cur, M2]가 될 것인데 두 값 모두 자기보다 작은 값이기 때문이다.
2. M1 ... M2 ... cur 또는 cur ... M1 ... M2 와 같이 외곽에 위치한다면 보존이 가능하다. M2는 항상 M1 보다 큰 값이고 두 풍선이 먼저 인접하기에 M1에 의해 M2는 제거되고 cur 풍선은 주어지는 단 한 번의 기회로 M1을 제거할 수 있다.

즉 우리는 지금 차례의 풍선이 제거가 가능한지 불가능한지를 알기 위해서는 해당 풍선이 최소값과 두번째 최소값 사이에 위치하고 있는지를 체크해봄으로써 파악할 수 있다. 그런데 여기서 우리가 두 개의 최솟값을 직접 찾아서 위의 과정을 수행하려고 한다면, 최솟값이 항상 외곽에 있음을 보장할 수 없기 때문에 한 번의 반복문으로는 생존가능한 모든 풍선의 경우의 수를 파악할 수가 없다.

때문에 우리는 주어진 풍선 배열에서 시작과 끝 값을 임의로 가장 작은 값 과 두번째로 작은 값으로 간주할 것이다. 실제로 둘 중에 무엇이 더 작은지는 중요하지 않다. 왜냐하면 반복문을 통해 이를 계속 체크해줄 것이기 때문이다. 여기까지의 과정을 먼저 코드로 보자.

let m1_idx = 0;
let m2_idx = a.length - 1;

let m1 = a[m1_idx];
let m2 = a[m2_idx];

따라서 m1 과 m2 라고 임의로 선정한 두 최솟값이 배열의 시작과 끝이기 때문에 이 둘 사이에 모든 풍선들이 배치된 형태를 가져올 수 있다. 위에서 두 개중에 누가 더 작은 지는 반복문에서 체크해준다고 했다. 따라서 우리는 반복문을 돌릴건데, 반복문의 탈출조건은 이분탐색과 유사하게 시작인덱스가 종료인덱스를 초과하는 시점이 될 것이다. 즉 m1 과 m2 를 비교하면서 누가 더 작은 값인지 체크하고, 더 큰 값의 인덱스를 조정해주며 다음 풍선을 가져오도록 하자.

// 시작 인덱스가 종료 인덱스를 벗어나면 반복 종료
while(m1_idx < m2_idx) {
  if(m1 > m2) {
    // m1이 더 크므로 m1과 인접한 다음 풍선을 탐색
    m1_idx++;
  }
  if(m1 < m2) {
    // m2가 더 크므로 m2와 인접한 다음 풍선을 탐색
    m2_idx--;
  }
}

위의 반복문을 통해 우리는 계속 최솟값을 갱신하면서 두 개의 최솟값을 외곽에 배치하는 구조를 유지할 수 있다. 그렇다면 이제 보존이 가능한 풍선과 그렇지 않은 풍선을 구분하는 조건이 필요하다. 다음을 생각해보자.

1. m1 > m2 인 경우, a[++m1_idx] 이 인접한 풍선이 된다.

   1-1. m1 > a[++m1_idx] 인 경우 m1 은 최솟값이 아니다.
   1-2. 즉 m1은 최솟값 외곽에 위치하는 형태가 되므로 보존이 가능하다. (answer 1증가)
   1-3. 기존의 m1 이 최솟값이 아니게 되었으므로 지금의 최솟값으로 갱신한다.

2. m1 < m2 인 경우, a[--m2_idx] 가 인접한 풍선이 된다.

   2-1. m2 > a[--m2_idx] 인 경우 m2 는 최솟값이 아니다.
   2-2. 즉 m2는 최솟값 외곽에 위치하는 형태가 되므로 보존이 가능하다. (answer 1증가)
   2-3. 기존의 m2 가 최솟값이 아니게 되었으므로 지금의 최솟값으로 갱신한다.

위의 과정을 모두 반복한 뒤 반복문을 빠져나오면 answer 에는 보존 가능한 풍선의 개수가 담겨 있을 것이다. 이때 다음을 주의해야 한다. 우리는 반복문에서 계속 두 개의 최솟값 풍선을 사용해서 탐색을 진행했다. 즉 두 개 중에 하나는 추가로 또 제거가 가능할 것 이다. 따라서 answer + 1 이 정확하게 문제에서 요구하는 반환값이 될 것이다. 이를 코드로 나타내면 다음과 같다.

let answer = 1;  // 반복문 내에서는 마지막 경우를 세주지 못해 1로 초기화하여 진행
let m1_idx = 0;   let m2_idx = a.length - 1;
let m1 = a[m1_idx];   let m2 = a[m2_idx];

while(m1_idx < m2_idx) {
  if(m1 > m2) {
    // 위에서는 과정을 위해 m1_idx++ 로 나타냈지만
    // 아래처럼 바로 비교할 수도 있다.
    if(m1 > a[++m1_idx]) {
      answer++;
      m1 = a[m1_idx];
    }
  } 
  if(m1 < m2) {
    // 위에서는 과정을 위해 m2_idx-- 로 나타냈지만
    // 아래처럼 바로 비교할 수도 있다.
    if(m2 > a[--m2_idx]) {
      answer++;
      m2 = a[m2_idx];
    }
  }
}

return answer;

해당 포스트에서는 위와 같이 투포인터를 이용해 O(N)의 시간복잡도로 풀었다. 하지만 앞에서 잠깐 언급한 바와 같이 다른 방식의 풀이도 가능할 것이다. 아래는 주석을 제외한 전체코드이다.

코드

function solution(a) {
  let answer = 1;
  let m1_idx = 0;   let m2_idx = a.length - 1;
  let m1 = a[m1_idx];   let m2 = a[m2_idx];
  
  while(m1_idx < m2_idx) {
    if(m1 > m2) {
      if(m1 > a[++m1_idx]) {
        answer++;
        m1 = a[m1_idx];
      }
    } 
    if(m1 < m2) {
      if(m2 > a[--m2_idx]) {
        answer++;
        m2 = a[m2_idx];
      }
    }
  }

  return answer;
}

출처

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