햄랑

공부했던 것들을 남기는 곳입니다:)

프로그래머스: 풍선 터트리기⭐⭐⭐

업데이트:     Updated:

카테고리:

태그: , , ,

난이도 ⭐⭐⭐
유형 : 구현

🧐 문제

문제 설명

일렬로 나열된 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

입출력 예 설명

접기/펼치기

입출력 예 #1

  • 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법
    1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
  • 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법
    1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
  • 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법
    1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.

3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

✏️ 나의 풀이

#include <bits/stdc++.h>
#include <climits>

using namespace std;

int solution(vector<int> vec) {
	// 풍선의 개수가 2개 이하라면, 모두 살릴 수 있다.
  int vec_size = vec.size();
  if(vec_size <= 2) return vec_size;
  
  // 각 위치 기준 오른쪽에 있는 값들 중 최솟값을 미리 계산하여 저장
  vector<int> right_min_vec(vec_size, INT_MAX);
  for(int i=vec.size()-1; i>0; i--) right_min_vec[i-1] = min(vec[i], right_min_vec[i]);
  
  // 현재 풍선이 왼쪽 최솟값과 오른쪽 최솟값보다 모두 큰 경우는 제외
	// 그렇지 않으면 살아남을 수 있으므로 answer 증가
  int answer = 2;
  int left_min = vec[0];
  for(int i=1; i<vec.size()-1; i++) {
    if(vec[i] > left_min && vec[i] > right_min_vec[i]) continue;
    answer++;
    
    if(vec[i] < left_min) left_min = vec[i];
  }
  
  return answer;
}

| 3 | 2 | 4 | 0 | 1 | | — | — | — | — | — |

풍선이 위와 같이 배열되어있다고 가정한다.

인접한 두 풍선 중, 숫자가 더 작은 풍선을 터뜨리는 행위를 스킬이라고 하겠다.

  • 3을 살리기
    1. 3의 오른쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    2. [3, 0]이 남았으므로 스킬을 한번 사용하여 3을 살릴 수 있다.
  • 2를 살리기
    1. 2의 왼쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    2. 2의 오른쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    3. [3, 2, 0]이 남았으므로 스킬을 한번 사용하여 2를 살릴 수 있다.
  • 4를 살리기
    1. 4의 왼쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    2. 4의 오른쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    3. [2, 4, 0]이 남았으므로 스킬 한번으로는 4를 살릴 수 없다.
  • 0을 살리기
    1. 0의 왼쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    2. 0의 오른쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    3. [2, 0, 1]이 남았으므로 스킬을 사용하지 않아도 0을 살릴 수 있다.
  • 1을 살리기
    1. 1의 왼쪽에 있는 값들끼리 대결시킨다. 이때 스킬을 사용하지 않는다.
    2. [0, 1]이 남았으므로 스킬을 한번 사용하여 1을 살릴 수 있다.

위의 과정을 살펴보면 알 수 있는 패턴이 있다.

  1. 왼쪽의 최소값과 오른쪽의 최소값을 구한다.
  2. (살릴려는 값 > 왼쪽 최소값 && 살릴려는 값 > 오른쪽 최소값)이 참이라면, 살릴 수 없다.
  3. 이 외의 경우는 모두 살릴 수 있다.

이 과정을 코드에 적용시키면 되는데, 주의해야할 점이 있다.

이중포문을 통해 이 문제를 해결하려 시도한다면, $O(N^2)$이 되어 시간 초과가 뜨게 된다.

그러므로 리스트에 미리 최소값을 구해놓는 과정을 통해 $O(N)$으로 만들어야 한다.

✔️ 다른 사람의 풀이

#include <string>
#include <vector>
#include <stack>

using namespace std;
int solution(vector<int> a) {
    int answer = a.size(); // 모든 풍선이 살아남는다 가정
    stack<int> stack; // 오름차순 유지를 위한 보조 스택
    for(int comp : a){
        while(!stack.empty() && comp < stack.top()){
            stack.pop(); // 오름차순이 깨지면 pop
            if(!stack.empty()) // 왼쪽에 더 작은 값이 있다는 것을 뜻한다.
                answer--; // pop된 값은 살아남을 수 없다.
        }
        stack.push(comp);
    }
    return answer;
}

기본적인 조건은 다음과 같다.

(살릴려는 값 > 왼쪽 최소값 && 살릴려는 값 > 오른쪽 최소값)이라면 풍선을 살릴 수 없다.

만약 오름차순으로 정렬되어 있다면, 모든 풍선이 살아남을 수 있다.

이 풀이의 요점은 스택을 사용하여 오름차순을 유지하도록 하면서,

  • 현재 값이 오름차순을 깨면, 스택에서 pop된다.
  • 만약, pop된 이후에도 stack에 값이 남아있다면, → 왼쪽에 더 작은 풍선이 남아있다. → 살아남지 못하므로, answer—;

stack은 이전 값들을 저장하며 오름차순 흐름을 유지해주는 도구이다.

그리고 그 오름차순을 유지해주는 이유는 왼쪽에 현재 값보다 작은 값이 없다는 것을 판별하기 위한 것이다.

| 3 | 2 | 4 | 0 | 1 | | — | — | — | — | — |

이전의 풍선 예시를 가져와서 살펴보면 다음과 같다.

Index 값 stack 변화 pop 발생 answer 변화
0 3 push 3   5
1 2 pop 3, push 2 ✅ pop 이후에 stack이 비어있음 → 5
2 4 push 4 ❌ 5
3 0 pop 4, pop 2, push 0 ✅✅ pop 이후 스택이 안비어있음 → 4
4 1 push 1 ❌ 4

굉장히 떠올리기 힘든, 신선한 풀이 방법이라는 생각이 든다.

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

참고