풍선 터트리기 ***** => 답은 안 올림

사용 알고리즘: 

사용 언어: java

 

 

- ‘나’인덱스를 기준으로 생각해서 왼쪽 세트와 오른쪽 세트 구하고 비교하기   - 일단 작은 값이 남는 게 국룰임 (기회 한 번만 사용해서 작은 값을 없앨 수 있음)   ‘나’ 기준으로   1. 왼쪽 세트 개수가 0이면 가능 (=내가 0 인덱스이면)   2. 오른쪽 세트 개수가 0이면 가능 (=내가 a.length -1 인덱스이면)   3. ~~ 나 ~~ 일 때가 문제인데   3-1. 나이상 나 나이상 ⇒ 가능 (양쪽 끝 만드는 과정에서 기회 삭제) ⇒ 하지만 양쪽 사이즈가 2,2였다면…?ㅎ…   3-2. 나이상 나 나이하 ⇒ 가능 (대신 기회가 남아있어야 함)   3-3. 나이하 나 나이상 ⇒ 가능 (대신 기회가 남아있어야 함)   3-4. 나이하 나 나이하 ⇒ 불가능

 

 

일단 시간초과 케이스

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        
        int len = a.length;
        if(len <= 3)
            return len;
        
        int[] leftMin = {a[0], 0}; //왼쪽 세트에서 가장 작은 값, 인덱스
        int[] rightMin = findMin(a, 1); //오른쪽 세트에서 가장 작은 값, 인덱스
        for(int i=0; i<len; i++) {
            if(i==0 || i==len - 1)
                answer++;//
            
            else {
                if(rightMin[1] == i) {//
                    if(leftMin[0] > a[i]) {
                        leftMin[0] = a[i];
                        leftMin[1] = i;
                    }
                    answer++;
                    rightMin = findMin(a, i+1);
                }
                else {
                    if(leftMin[0] > a[i]) {
                        leftMin[0] = a[i];
                        leftMin[1] = i;
                        answer++;
                    }
                    
                }
                
            }
        }
        
        return answer;
    }
    
    public int[] findMin(int[] a, int startIdx) {
        int m = 1000000000 ;
        int idx = startIdx;
        for(int i=startIdx; i<a.length; i++) {
            if(m > a[i]) {
                m = a[i];
                idx = i;
            }
        }
        return new int[] {m, idx};
    }
}

 

아무래도 findMin() 메서드에서 시간이 부족해질 거 같다. 이를 해결하기 위해 우선순위 큐를 써서 작은 값부터 순서대로 저장해야 하나?라고 생각했지만... 지금보다 빨라지더라도 여전히 시간초과일 거 같다는 느낌이 들었다...

 

결국 사람들이 올린 답을 확인해보는데....

헐!;; 이런 간단한 방법이;;;