[프로그래머스 Level 3] 풍선 터트리기

문제

 

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

 

---

풀이

 

원리만 알면 간단한 문제였다. 처음에는 기준 풍선 좌우의 최소값을 구할 때 매번 탐색했고, 시간 복잡도가 O(3n)정도 된다고 한다. 그래서 사용한 알고리즘이 바로 투포인터, 투포인터를 사용하면 O(n) 복잡도로 해결이 가능하다.

 

로직을 설명하자면,

 

1. 처음 시작 포인터를 배열의 처음과 끝 인덱스로 설정한다.
2. 또한, 왼쪽의 최소값과 오른쪽의 최소값을 해당 인덱스의 값으로 설정한다.
3. 조건에 맞춰 탐색을 진행한다.
   • 조건 1 : 두 포인터의 값 중에서 큰 값을 갖는 포인터를 기준으로 한다.
   • 조건 2 : ①기준 포인터 방향의 최소값과 ②배열의 중앙과 가까운 방향으로 한 칸 떨어진 원소의 값을 비교한다.
     • ex) 오른쪽 포인터라면 포인터의 왼쪽 값, 왼쪽 포인터라면 포인터의 오른쪽 값
     • 조건 2-1 : ①이 더 크다면, 풍선을 남기는 것이 가능하므로 answer에 1을 더한다.
     • 조건 2-2 : ②가 더 크다면, 풍선을 남기는 것이 불가능하다.
     • 조건 2-3 : 배열의 중앙을 향해서 포인터를 한 칸 이동한다.
   • 조건 3 : 왼쪽 포인터가 오른쪽 포인터를 만나면 탐색을 종료한다.

즉, 끝까지 살아남는 풍선을 기준으로 왼쪽과 오른쪽의 최소값을 비교해서 하나라도 크면 살아남을 수 있다. 각 방향에서 최소값보다 큰 풍선은 터지고, 그 중 가장 작은 값이 살아남은 것이기 때문이다. 그러면 둘 중 한쪽이 기준값보다 작더라도 한 번은 작은 값의 풍선을 터트릴 수 있기 때문에 정답을 구할 수 있다.

 

더 쉽게 설명하기 위해 [5, 6, 1, 4, 7]이라는 배열로 예를 들어 보자.

 

시작 인덱스와 끝 인덱스를 두 포인터로 설정하면, 0과 4가 된다. 또한, 왼쪽의 최소값은 5, 오른쪽의 최소값을 7이 된다.

 

두 포인터가 가리키는 값을 비교해보면 5와 7로 오른쪽이 더 크다. 그렇다면 오른쪽의 최소값(=7)과 한 칸 왼쪽의 원소(=4, 배열의 중앙과 가까운 방향)를 비교한다. 오른쪽 최소값이 더 크므로, 풍선 4는 끝까지 살아남을 수 있다. 이후 오른쪽 최소값을 4로 갱신하고, 오른쪽 포인터를 한 칸 왼쪽으로 이동한다.

 

다시 포인터가 가리키는 값을 비교해보면 5와 4로 왼쪽이 더 크다. 그렇다면 왼쪽의 최소값(=5)과 한 칸 오른쪽의 원소(=6)를 비교한다. 왼쪽의 최소값이 더 작으므로, 풍선 6은 끝까지 살아남을 수 없다. 최소값은 갱신하지 않고, 포인터만 오른쪽으로 한 칸 이동한다.

 

다음 두 포인터가 가리키는 값을 비교해보면 6과 4로 왼쪽이 더 크다. 그렇다면 왼쪽의 최소값(=5)과 한 칸 오른쪽의 원소(=1)를 비교한다. 왼쪽의 최소값이 더 크므로, 풍선 1은 끝까지 살아남을 수 있다. 이후 왼쪽의 최소값을 1로 갱신하고, 왼쪽 포인터를 오른쪽으로 한 칸 이동한다.

 

마찬가지로 포인터들이 가리키는 값 1과 4를 비교하면 조건에 일치하는 것을 알 수 있다.

 

사실 양 끝에 있는 5, 7은 항상 살아남을 수 있고, 탐색하면서 1, 4가 끝까지 살아남을 수 있음을 알게된다. 하지만 위의 로직대로라면 탐색을 통해 구할 수 있는 풍선의 개수는 3개이다. 그래서 answer의 초기값을 1로 설정해두었다.

 

public class Solution {

    public int solution(int[] a) {
        int answer = 1;
        int left = 0, right = a.length-1;
        int lMin = a[left], rMin = a[right];

        while(left < right) {
            if(a[left] < a[right]) {
                if(rMin > a[right-1]) {
                    rMin = a[right-1];
                    answer++;
                }
                right--;
            }else {
                if(lMin > a[left+1]) {
                    lMin = a[left+1];
                    answer++;
                }
                left++;
            }
        }
        return answer;
    }
}