[PG] 풍선 터트리기 JAVA

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

코딩테스트 연습 - 풍선 터트리기

문제 설명

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

---

입출력 예

aresult

[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개입니다.

 

 

 

 

 

 

 

풀이 .

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

        int[][] ans = new int[a.length][2];  // [i][0], [i][1] 중 하나만 1이면 지울 수 있음을 의미
        for(int i = 1; i <= a.length - 2; i++) {
            if(left > a[i]) {  // 끝점보다 작으면 지울 수 있다
                left = a[i];  // 더 작은 놈이 나왔으니 왼쪽 최소값 변경
                ans[i][0] = 1;
            }
        }
        for(int i = a.length - 2; i >= 1; i--) {
            if(right > a[i]) {  // 끝점보다 작으면 지울 수 있다
                right = a[i];  // 더 작은 놈이 나왔으니 오른쪽 최소값 변경
                ans[i][1] = 1;
            }
        }
        for(int i = 1; i <= a.length - 2; i++) {
            if(ans[i][0] == 1 || ans[i][1] == 1) {
                answer += 1;
            }
        }

        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] a = {-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
        int ans = sol.solution(a);
        System.out.println(ans);
    }
}

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

( 절취선 나오기 전까지 푸념 주의 )

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

좌절감의 끝을 맛봤다.

 

도저히 혼자서는 방법을 떠올릴 수 없었다. 답을 봐도 한참동안 이해가 안 됐다.

 

나는 이런 유형의 문제가 너무 싫다.

 

DFS, BFS, 백트래킹, 브루트포스, 문자열.. 하다못해 그 DP마저도 풀다보면 유형이 익숙해지고 문제를 읽었을 때 "아, 이걸 적용해야겠구나" 하는 감이 왔다. (사실 이것도 완벽하게는 아니지만.. 그래도 확실히 어느정도는 느낌이 왔다)

 

근데 이런 식의 관찰력? 직관력?을 통해 조건을 찾아내고 그 조건에 따라 전개하는 방식은 도저히, 정말 도저히 모르겠다.

 

알고리즘이라는 영역이 애초에 지능의 영역이긴 하지만 그래도 몇몇 유형들은 경험치를 쌓아나갈수록 어느정도는 성장하는 느낌을 받을 수 있었지만.. 이건 그것조차 안 되는 거 같다. 

 

답을 확인해도 "이게 뭔소리지?" 그러다가 겨우겨우 이해를 하면 "대체 어떻게 이런 생각을 하지?" 그냥 사람을 너무 초라하게 만든다.

 

근데 이런 게 또 남들이 볼 때는 그렇게 엄청 어려운 문제는 아닌 듯 하다. 그 사실이 좌절감을 더 증폭시킨다.

 

사실 아직도 완벽하게 이해하진 못했다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

 

문제의 키 포인트는 다음 문장이다.

 

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

 

일단, 처음으로 양 끝 기준점이 되는 첫 원소와 마지막 원소 둘은 반드시 정답에 포함될 수 있다.

(이것도 왜 그런지 모르겠다..)

 

마지막까지 살릴 수 있는지 없는지를 판단하는 원소의 양 옆에 기준점 두 개를 잡는다.

대상 원소 하나 + 기준점 원소 둘 이 셋 중에서 대상 원소가 가장 큰 원소가 아니라면 대상 원소를 지울 수 있다.

 

다른 원소들을 전부 먼저 지우고 이 셋만 남아있을 때 (이떄 세 원소는 연속하는 위치일 것임) 만약 가운데에 위치한 대상 원소가 가장 크다면? 그럼 더 작은 양 옆의 원소를 모두 날릴 수 없다. (더 작은 원소 삭제는 한 번만 가능하니까)

(근데.. 더 큰 원소만 지우면서  이 셋만 남기는 게 가능하다는 것이 어떻게 보장되지? 이걸 모르겠다)

 

양 쪽 끝점에 대한 검사를 반복 한 번으로 동시에 하는 코드도 있었지만 그건 이해를 못 하겠어서 다른 방법을 보고 풀었다. (엄밀히 말하면 내가 푼 것도 아니긴 하지만)

 

1. 왼쪽 끝점보다 대상 원소가 작은지 검사. 

2. 오른쪽 끝점보다 대상 원소가 작은지 검사.

(1, 2 단계에서 대상 원소가 더 작아서 정답에 포함되는 경우엔 끝점을 변경. 이것도 왜 하는지 이해 못했다)

3. 둘 중 하나라도 1이라면 어쨌든 세 원소 중 가장 큰 건 아니라는 뜻이니 정답에 포함됨.

 

 

다 적고보니 그냥 아는 게 없는 수준이네 ㅋㅋ 이 글 자체를 쓰지 말 걸 그랬나.. 

 

 

하