[월간 코드 챌린지1] 풍선 터트리기 (java)

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

프로그래머스

 

[문제풀이 전]

(문제 해결 전 여러가지 시도)

문제를 코드로 구현해서 실행하면, 시간초과나 메모리초과로 문제를 해결할 수 없다. 

 

해당 문제는 작은 수를 선택하는 것은 한번만 선택 가능하다는 규칙이 있다.

이를 이용하면, 특정 값 기준으로 양쪽에 자신보다 작은 값이 있다면 터트리지 못한다는 뜻이다. (-> 이렇게 되면 최소 두번은 작은 수를 터트려야하기 때문)

하지만, 이걸 그대로 구현하면 n^2이 되어 시간초과가 된다.

 

(해결방법)

풍선이 터지려면 한 쪽에는 기준 값보다 큰값만 있어야 한다, 이를 이용하면 최솟값을 갱신시키는 값은 정답이 될 수 있다는 의미가 된다. (왜? 최솟값이 바꼈다는 것은 앞의 인덱스에 있는 모든 값보다 작은 수라는 뜻이다. 즉, 한 쪽은 현재 값보다 모두 큰 값이라는 의미이다.)

해당 방법은 2n정도의 시간이 걸려 시간초과 없이 해결 가능하다. 

 

이를 입출력 예제로 확인해보면 아래와 같다. 

-16	27	65	-2	58	-92	-71	-68	-61	-33
-16	-16	-16	-16	-16	-92	-92	-92	-92	-92

문제에서는 방향이 딱히 정해져있지않고, 인접한 노드라고만 언급했으므로 반대 방향도 체크해준다.

-33	-61	-68	-71	-92	58	-2	65	27	-16
-33	-61	-68	-71	-92	-92	-92	-92	-92	-92

여기서 배열 a의 최솟값은 두방향 모두 체크되므로 중복에 주의해야한다. 

 

[문제풀이]

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 1;
        int min=a[0]; 
        for(int i=1;i<a.length;i++){ //→
            if(min>a[i]){
                min = a[i];
                answer++;
            }
        }
        min = a[a.length-1];
        for(int i=a.length-2;i>=0;i--){ //←
            if(min>a[i]){
                min=a[i];
                answer++;
            }
        }
        return answer;
    }
}

min	현재 인덱스까지 가장 작은 값을 저장하는 변수
for(int i=1;i<a.length;i++){}	인덱스 1부터 배열 끝까지 탐색하며 최솟값이 변경될 때마다 answer++;
for(int i=a.length-2;i>=0;i--){}	인덱스 a,length-1부터 0까지 탐색하며 최솟값이 변경될 때마다 answer++;

answer 초기값 및 중복 관련

  - 배열의 첫번째와 마지막 값은 무조건 터트릴 수 있다(양쪽이 아니라 한쪽방향만 있기 때문). 따라서 초기값은 1로 설정한다.

  - 배열의 최솟값은 중복되어 체크된다, 이는 첫번째 값을 터트릴 수 있다는 의미로 초기값을 1로 설정한 것 과 달리 마지막 값은 +1을 하지않으면서 해결 가능하다. 

 

 

[comment]

재귀함수로 구현가능하겠는데? 하고 효율성 생각안하고 바로 구현한게 아쉽다. 그리고 재귀함수보다 새로 생각해서 푼 코드가 더 쉽게 구현할 수 있었다.. 

숫자 + 규칙이 있으면, 새롭게 해결할 수 있는 방법이 있는게 보통인데,, 바로 캐치하지 못한 것이 아쉽다. 그래도 최근에 dfs 같이 자주 나오는 유형만 풀다가 새로운 문제 풀어서 재밌었다