[월간 코딩 챌린지] 풍선 터뜨리기 - Level3

📍문제 설명 

일렬로 나열된 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개입니다.

 

 🔎 처음 생각한 아이디어  

처음에 남길 수 있는 경우의 수를 다 구해야 하나?라고 생각이 들어 막막했다.

손으로 적어가며 경우의 수를 나누고 있다가 이건 도저히 아닌 것 같아서

질문하기에서 누군가 남겨주신 접근법을 보게되었다.

끝까지 남기려는 풍선을 기준으로 좌, 우 구간의 최솟값을 구했을 때
터뜨리려는 풍선의 값은 두 최솟값보다 크지 않아야 합니다.
한 번은 작은 풍선을 터트릴 수 있기 때문에 터트리려는 푸선이
좌, 우 최소값 중 하나보다는 클 수 있어도, 둘 보다 커버리면 남길 수 없습니다.
Only one max = 큰 수는 하나까지만 허용
좌에서 우로 최솟값을 갱신하며 배열에 넣고, 우에서 좌로 동일하게 해 주고
마지막에 두 최솟값보다 크지 않나 보면서 확인해줍니다.

라는 글에서 힌트를 얻었다.

천재..!!

 

배열 중 처음과 끝 풍선은 무조건 끝까지 남길 수 있다. 

그렇다면 그 사이 값을 검사해야하는데, 

현재 검사하는 사이값을 A라고 하겠다. 

그리고 좌우 값을 각각 l_min, r_min값이라고 하겠다.

A가   l_min, r_min 보다 큰 경우만 남길 수 없다.

왜냐? 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있기 때문이다.

 l_min,  A , r_min 이렇게 풍선이 존재할 때

l_min, r_minr_min 중 어떤 값을 터트려도 무조건 A를 터트려야 하는 상황이 온다.

그렇기 때문에 A를 남기려면 A가 가진 값이

1. l_min < A < r_min
2. r_min < A < l_min
3. A < r_min , l_min

이여야 남길 수 있으며 

A > l_min, r_min 이면 불가능하다. 

 

 

 ✏️ 작성한 코드 

package monthly_coding_challenge;

public class 풍선터뜨리기 {


		public int solution(int[] a) {
			 int answer = 2;
				int l_min = a[0];
				int r_min = a[a.length-1];
				
				int x = 1, y = a.length-2;
			   
				for(int i =1;i<a.length-1;i++) {
					
					if(l_min > r_min) { // 큰값보다 a[]값이 더 크면 a[] 값은 남길 수 없음 
				
						if(l_min > a[x]) {
							answer++;
							l_min = a[x];
						}
						x++;
					}else {
						
						if(r_min>a[y]) {
							answer++;
							r_min = a[y];
						}
						y--;
					}
					
					
				}
			   
			  
				
				return answer;
		}
	

}
/*
 정확성  테스트
테스트 1 〉	통과 (0.02ms, 72.9MB)
테스트 2 〉	통과 (0.01ms, 72.5MB)
테스트 3 〉	통과 (0.04ms, 76.6MB)
테스트 4 〉	통과 (1.96ms, 83.5MB)
테스트 5 〉	통과 (4.15ms, 121MB)
테스트 6 〉	통과 (6.52ms, 118MB)
테스트 7 〉	통과 (8.56ms, 130MB)
테스트 8 〉	통과 (7.22ms, 138MB)
테스트 9 〉	통과 (4.86ms, 125MB)
테스트 10 〉	통과 (4.98ms, 128MB)
테스트 11 〉	통과 (9.68ms, 122MB)
테스트 12 〉	통과 (10.79ms, 139MB)
테스트 13 〉	통과 (9.35ms, 133MB)
테스트 14 〉	통과 (11.88ms, 129MB)
테스트 15 〉	통과 (8.74ms, 142MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
*/

 

 🖍 알게 된 점 

다른 사람 풀이 중 이마를 탁 치게 된 🔥🔥

   public int solution(int[] a) {
        int answer = 0;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        HashSet<Integer> hs = new HashSet<>();
        // int[][] dp=new int[a.length][2];
        for(int i=0;i<a.length;i++){
            min1=Math.min(min1,a[i]);
            min2=Math.min(min2,a[a.length-1-i]);
            hs.add(min1);
            hs.add(min2);
            // dp[i][0]=min1;
            // dp[a.length-1-i][1]=min2;

        }
        // for(int i=0;i<dp.length;i++){
        //     System.out.println(dp[i][0]+" "+dp[i][1]);
        // }
        return hs.size();
    }

 

 

 

 

 

 

하드 코딩하는 방식으로 접근하지 말고
규칙을 찾아보자.