[프로그래머스] 풍선 터뜨리기 python, java

문제 풀이

접근 방법

어떤 알고리즘인지 전혀 맥락을 못잡다가 문제 푼 지 35분이 경과되어서 알게 되었습니다.

2개의 임의의 풍선 중 크기가 큰 풍선을 터뜨려야 한다.
단, 크기가 작은 풍선은 딱 1번만 터뜨릴 수 있다.
풍선을 터뜨렸다면 풍선의 빈 공간을 다시 채운다(양 옆의 풍선을 당겨준다)
최후에 1개의 풍선이 남았을 때, 절대 남을 수 없는 풍선의 갯수를 구하자

DFS인가? 생각했다가 N의 크기를 보고 절대 아니라고 판단했고, O(N)에 끝내야 한다는 것으로 생각을 굳혔습니다.

다른 측면에서 생각해볼까요?

어떤 임의의 풍선을 선택하고 왼쪽 또는 오른쪽 풍선 중 하나를 터뜨린다고 생각해 봅시다. (선택한 임의의 풍선은 끝까지 살려 놓겠다고 가정합시다)

이 상황에서 선택한 풍선이 살아 남는 조건은 뭘까요?

왼쪽 또는 오른쪽에서 당겨지는 풍선이 크거나 또는 1회만 작은 풍선이 온다면 이 풍선은 살아남습니다.

반대로 생각하면 2회 이상 작은 풍선이 온다면 살아 남을 수 없습니다

구현 방법

저는 2가지 Array를 사용했습니다.

왼쪽에서 접근하여 최솟값을 저장 leftMin
오른쪽에서 접근하여 최솟값을 저장 rightMin

임의의 a[i]가 leftMin[i], rightMin[i] 두 수보다 크다면 해당 a[i]는 살아남을 수 없습니다.

그 때 카운팅을 해주고 a의 갯수에서 카운팅한 수를 빼주면 정답을 도출할 수 있습니다.

a	-16	27	65	-2	58	-92	-71	-68	-61	-33
left	-16	-16	-16	-16	-16	-92	-92	-92	-92	-92
right	-92	-92	-92	-92	-92	-92	-71	-68	-61	-33

입출력 예제 2번과 동일한 케이스일 때 left와 right는 위와 같습니다.

붉은색으로 표시 된 a[i] 값들은 left, right에 해당하는 수보다 크기 때문에 살아남을 수 없습니다.

그렇기 때문에 최종적으로 10-4 연산을 하여 6이라는 정답이 나오게 됩니다.

소스 코드

Python

def solution(a):
    answer = 0
    leftMin = [10e9+1]*len(a)
    rightMin = [10e9+1]*len(a)
    leftMin[0]=a[0]
    for i in range(1,len(a)):
        leftMin[i] = min(leftMin[i-1],a[i])
    rightMin[-1]=a[-1]
    for i in range(len(a)-2,-1,-1):
        rightMin[i] = min(rightMin[i+1],a[i])
    for i in range(len(a)):
        if leftMin[i]<a[i] and rightMin[i]<a[i]:
            answer+=1
    return len(a)-answer

java

public int solution(int[] a) {
	    	int N = a.length;
	        int answer = 0;	        
	        int leftMin[] = new int[N];
	        int rightMin[] = new int[N];
	        leftMin[0]=a[0];//시작점에 index 0 삽입
	        for(int i =1;i<N;i++)
	        	leftMin[i] = Math.min(leftMin[i-1],a[i]);
	        
	        rightMin[N-1]=a[N-1];//시작점에 index 끝 삽입
	        for(int i =N-2;i>=0;i--)
	        	rightMin[i] = Math.min(rightMin[i+1],a[i]);
	        
	        for(int i =0;i<N;i++)
	        	if(a[i]>leftMin[i] && a[i]>rightMin[i])
	        		answer++;
	        return N-answer;
	    }