(코테)프로그래머스_풍선 터트리기 *dp

 

 

문제 링크

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/68646

 

 

 

 

최초 제시한 답

class Solution {
    public int solution(int[] a) {
        int answer = 0;     
        //orgin  -16, 27,65, -2, 58, -92,-71,-68,-61,-33
        //left   -92,-92 -92 -92 -92 -92,-71,-68,-61,-33
        //right  -16  -16 -16 -16-16 -92,-92,-92,-92,-92
        //        X   O    O   O  O   X   X   X   X  X 
        // 좌누적 , 우누적중 하나라도 최솟값보다 작거나 같으면 무조건 살아남음.
        int len = a.length;
        int[] left = new int[len];
        int[] right = new int[len];

        left[0] = a[0];
        right[len-1] = a[len-1];


        for(int i=1;i<len;i++){
              if(a[i]<=left[i-1]){
                 left[i]=a[i];                              
              }else{
                  left[i]=left[i-1];
              }
        }
        for(int i=len-2;i>=0;i--){
            if(a[i]<=right[i+1]){
              right[i]=a[i];  
            }else{
              right[i]=right[i+1];
            }
        }

        for(int i=0;i<len;i++){
            if(a[i]<=left[i] || a[i]<=right[i]){
                answer++;                            
            }
        }


        return answer;
    }
}

 

 

이후 리팩토링한 코드

 

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int answer = 0;
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        Set<Integer> result = new HashSet<>();
        int len=a.length;

        
        for(int i =0;i<len;i++){            
            
            //좌 계산
            if(a[i]<left){
                left = a[i];
                result.add(i);
            }
            
            //우 계산
            int j = len-1-i;
           if(a[j]<right){               
                right = a[j];
                result.add(j);
            }
            
        }
        
        
        return result.size();
    }
}

 

 

회고.

1. 리팩토링전

int[] 배열 두개로 왼쪽 누적 기록  오른쪽 누적 기록으로 
원본 배열 인덱스에서 왼누,오누 값에서 둘 중 하나라도 최소값보다 작거나 같은 케이스가 존재하면 살아남는다. 

역으로 작은 케이스가 없다면 넘어가다 무조건 터지게 될거니 

 

 

2.리팩토링 후 

for문 한번으로 
int 기본형에  left, rigth로  최솟값 갱신시키며 conuting

for문 한 번에 두 개 값 동시에 처리 set을 중복 인덱스 방지.

현재 인덱스에서 이전 left 혹은 rigth  최솟값보다 더 작으면 counting 

왜냐면 한쪽 방향으로 최솟값이니 살아남을 수  있음. 
left,rigth에 모두 해당 최솟값 해당 안되면  무조건 죽게됨.

 

 

결론.

리팩토링 전은  int[] 배열로 dp  생성 

리팩토링 후  int 에  최솟값 갱신 시키며 for문 한번으로 계산. (set으로 인덱스 중복 방지)