[C#] 풍선 터트리기

프로그래머스 문제

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

풀이 후기

1. 분석

느낌은 트리인거 같긴 한데... 자세히 보니까 그건 또 아닌거 같고 DP 느낌도 나긴하고... 그냥 되는대로 풀어보자 하고, 테스트 케이스 2번에서 -2 잡고 왜 안되는지 끄적이다 보니까 불가능한 이유를 알아챘다.

'큰 풍선 터뜨리기' 기회 안쓰고 해당 인덱스만 남게 풍선을 터뜨리다 보면, 결국 인덱스 기준으로 왼쪽에서 가장 작은 숫자, 오른쪽에서 가장 작은 숫자가 남게 되는데 두 숫자 모두 해당 인덱스의 숫자보다 작으면 '큰 풍선 터뜨리기' 기회를 한 번 밖에 쓸 수 없기 때문에 불가능해진다.

[-16,27,65,-2,58,-92,-71,-68,-61,-33]
-2를 기준으로 본다면.. 왼쪽에서는 -16, 오른쪽에서는 -92 인데 이렇게 되면 '큰 풍선 터뜨리기'를 사용해도 불가능이니까 정답이 아님.

그래서 시작 지점, 끝 지점 부터 작은 숫자들을 모아둔 배열을 만들어서 index - 1, index + 1 값을 비교해서 정답을 추출하기로 했다. 모아둔 배열을 만든다는 점에서 시간 초과가 좀 걱정됬는데, 다행히 한번에 통과.

2. 실행 결과

3. 코드

using System;

public class Solution {
    public int solution(int[] a) {
        var len = a.Length;
        
        var leftMinArr = new int[len];
        var leftMin = Int32.MaxValue;
        
        var rightMinArr = new int[len];
        var rightMin = Int32.MaxValue;
        
        var count = len;
        
        var lenFront = 0;
        var lenBack = len - 1;
        
        while(0 < count){
            if(a[lenFront] < leftMin){
                leftMinArr[lenFront] = a[lenFront];
                leftMin = a[lenFront];
            }
            else
            {
                leftMinArr[lenFront] = leftMin;
            }
            
            if(a[lenBack] < rightMin){
                rightMinArr[lenBack] = a[lenBack];
                rightMin = a[lenBack];
            }
            else
            {
                rightMinArr[lenBack] = rightMin;
            }

            lenFront++;
            lenBack--;
            count--;
        }
        
        var answer = 2;
        
        for(int i = 1; i < len - 1; i++){
            var con1 = leftMinArr[i - 1] < a[i];
            var con2 = rightMinArr[i + 1] < a[i];
            
            if(!(con1 && con2)){
                answer++;
            }
        }
    
        return answer;
    }
}