강승현입니다
article thumbnail
반응형

 

문제로이동

 

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

[-16,27,65,-2,58,-92,-71,-68,-61,-33] 6

programmers.co.kr


목차

     


    Python3
    java

    문제 풀이

    접근 방법

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

     

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

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

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

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

     

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

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

     

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

    구현 방법

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

    1. 왼쪽에서 접근하여 최솟값을 저장 leftMin
    2. 오른쪽에서 접근하여 최솟값을 저장 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;
    	    }
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    profile on loading

    Loading...