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

참고 : programmers.co.kr/learn/courses/30/lessons/68646

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

 

 

- 풀이 보고 푼 문제

- 일반적 로직 구현 문제

- ex) [1,2,3] 의 경우 : 양 끝인 1,3은 무조건 가능하다
*(오른쪽 끝일 경우 : 왼쪽 끝에서 오른쪽 마지막 전까지 작은 숫자를 선택(큰 풍선 터트리기는 무한대로 가능) 마지막에 숫자가 크던 작던 오른쪽 끝 숫자 선택 가능, 왜냐하면 작은 것을 한번 터트릴 수 있는 기회가 남아 있기 때문)
*(왼쪽 끝일 경우 : 오른쪽 끝에서 왼쪽 마지막 전까지 작은 숫자를 선택(큰 풍선 터트리기는 무한대로 가능) 마지막에 숫자가 크던 작던 왼쪽 끝 숫자 선택 가능)

- ex) [1,2,3] 가운데 숫자의 경우 : 2는 무조건 가능하다.

가운데 숫자를 뺀 나머지 숫자를 기준으로 왼쪽의 최소값, 오른쪽의 최소값을 가지고 있다고 가정할 때,

적은 풍선을 한번만 터트리는 것이 가능하기 때문에 불가능한 경우의 수는 왼쪽 최소값, 오른쪽 최소값이 모두 가운데 숫자보다 적어야 한다.
(ex) [1,4,3] 의 경우 : [3,4] 로 적은 숫자 풍선을 터트림 = 4 [1,4] 로는 적은 숫자를 터트릴 수 없기 때문에 남을 수 없다. )

 

 

 

class Solution {
    public int solution(int[] a) {
        int answer = 2; // 처음과 끝은 무조건 가능 (ex.왼쪽 끝 : 오른쪽 부터 쭉 작은 숫자 선택하다가 왼쪽 끝에서 작은 or 큰 숫자 선택);
        int l = a[0];
        int r = a[a.length-1];
        for(int i=1; i<a.length-1; i++) {
            // 가운데 숫자 확인
            if(l > a[i]) {
                l = a[i];
                answer++;
            }
            if(r > a[a.length-1-i]) {
                r = a[a.length-1-i];
                answer++;
            }
        }
        return l==r ? --answer : answer;
    }
}