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

정민주·2024년 11월 15일

코테

목록 보기

61/95

⭐ 문제링크

문제 요약

n개의 나열된 풍선

임의의 인접한 두 개의 풍선 중 하나를 터트림
인접한 풍선 중 번호가 더 작은 풍선을 터트리는 건 최대 1 번.
기본적으로는 번호가 더 큰 풍선을 터트려야 함.

결론
: 가장 마지막까지 남아있을 수 있는 풍선의 개수 구하기

풀이

해당 문제는 2가지 전제를 가진다.
1. 가장 왼쪽, 오른쪽 풍선은 살아남을 수 있다.
2. 양 옆 풍선이 둘 다 i번째 풍선보다 더 작으면 i번째 풍선만 남기는 것이 불가능하다.

✅ 2가지 배열 left, right를 만든다.

left : 현재 내 인덱스(i)에 대해 왼쪽의 수들 중, 가장 작은 값 넣음
right : 현재 내 인덱스(i)에 대해 오른쪽의 수들 중, 가장 큰 값 들어감

✅ 최종적 for문을 돌며, 양 옆 풍선 모두가 i번째 풍선보다 작은지 체크한다.

양 옆 풍선이 모두 작다면, 해당 풍선을 살아남을 수 없다.
양 옆 풍선이 하나라도 크다면, 해당 풍선은 살아남을 수 있다.

코드

✅ 2가지 배열 left, right를 만든다.

		int left[] = new int[a.length];
        int right[] = new int[a.length];
        
        //현재 내 인덱스(i)에 대해 왼쪽의 수들 중, 가장 작은 값 들어감
        int min=a[0];
        for(int i=1; i<a.length-1; i++){
            left[i]=min;
            if(a[i]<min) {
                min = a[i];
            }
        } 
        
        //현재 내 인덱스(i)에 대해 오른쪽의 수들 중, 가장 큰 값 들어감
        min = a[a.length-1];
        for(int i=a.length-2; i>0; i--){
            right[i]=min;
            if(a[i]<min){
                min=a[i];
            }
        }

✅ 최종적 for문을 돌며, 양 옆 풍선 모두가 i번째 풍선보다 작은지 체크한다.

		////양 옆의 최솟값이 둘 다 i 보다 작으면 살아남기 불가능.
		for(int i=1; i<a.length-1; i++){
            if(left[i] < a[i] && right[i] < a[i]) continue;
            answer++;
        }

✅ 전체 코드

class Solution {
    public int solution(int[] a) {
        int answer = 2; //가장 맨 끝 풍선 2개는 살아남음
        

        int left[] = new int[a.length];
        int right[] = new int[a.length];
        
        //현재 내 인덱스(i)에 대해 왼쪽의 수들 중, 가장 작은 값 들어감
        int min=a[0];
        for(int i=1; i<a.length-1; i++){
            left[i]=min;
            if(a[i]<min) {
                min = a[i];
            }
        }
        
        //현재 내 인덱스(i)에 대해 오른쪽의 수들 중, 가장 큰 값 들어감
        min = a[a.length-1];
        for(int i=a.length-2; i>0; i--){
            right[i]=min;
            if(a[i]<min){
                min=a[i];
            }
        }
        
        //양 옆의 최솟값이 둘 다 i 보다 작으면 살아남기 불가능.
        for(int i=1; i<a.length-1; i++){
            if(left[i] < a[i] && right[i] < a[i]) continue;
            answer++;
        }
        
        return answer;
    }
}