<Lv.3> 풍선 터트리기 (프로그래머스 : C#)

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

📕 문제 설명

풍선이 1개만 남을 때 까지 다음의 과정을 반복한다.
1. 임의의 인접한 두 풍선 중 하나 터트리기
2. 터진 풍선 사이 빈 공간 없도록 중앙으로 밀착

인접한 두 풍선 중 번호가 더 작은 풍선 터트리는 행위는 최대 1번만 가능할 때 최후까지 남기는 것이 가능한 풍선들 개수 반환하기

• Input
  풍선 번호 배열 a
• Output
  최후로 남길 수 있는 풍선 개수

예제

풀이

인접한 풍선 중 한 번만 작은 번호를 터트릴 수 있다. 그래서 i번째 풍선을 터트릴 수 있는 조건은 다음과 같다.

=> i의 왼쪽과 오른쪽에 제일 낮은 번호의 풍선들만 남겼을 때 그 중 i보다 큰게 한 개 이상인 경우

그래서 왼쪽과 오른쪽의 최솟값을 나타내는 두 배열을 선언한 후 i번째 보다 큰게 있는지 확인하는 식으로 코드를 작성했다. 여기서 한 가지 포인트는 양끝의 경우 본인 이전과 후의 값이 없어서 그냥 최대를 가지는 풍선을 하나씩 뒀다고 가정하고 진행한다.

using System;

public class Solution {
    public int solution(int[] a) {
        if (a.Length == 1) return 1;
        int n = a.Length;
        
        int answer = 0;
        // 맨 끝 양옆 비교 위해 1개씩 붙임 
        int[] leftMinDp = new int[n];
        int[] rightMinDp = new int[n];
        
        leftMinDp[0] = 1000000000;
        rightMinDp[n-1] = 1000000000;
        
        int leftMin = 1000000000;
        int rightMin = 1000000000;
        
        // dp 값 넣기
        for (int i = 0; i < n-1; i++)
        {
            leftMin = Math.Min(leftMin, a[i]);
            rightMin = Math.Min(rightMin, a[n-1-i]);
            
            leftMinDp[i+1] = leftMin;
            rightMinDp[n-2-i] = rightMin;
        }
        // 터트릴 수 있는지 확인 (양 옆 제일 작은 풍선 남길 때 나보다 큰 거 1개 이상 존재하면 터트리기 가능)
        for (int i = 0; i < n; i++)
        {
            if (leftMinDp[i] > a[i] || rightMinDp[i] > a[i])
            {
                answer += 1;
            }
        }
        
        return answer;
    }
}

결과