[프로그래머스 C#] Lv.3 풍선 터트리기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

임의의 두 풍선을 선택했을 때 숫자가 큰 풍선을 무조건 터트려야 하고, 작은 풍선은 단 한번만 터트릴 수 있는 조건의 모든 경우의 수에서 마지막 풍선으로 남을 수 있는 개수를 구하는 문제

 

1) 마지막 풍선이 될 수 있는지 판별

- 현재 인덱스를 기준으로 좌우 중 한쪽 방향에 나보다 작은 숫자를 가진 풍선이 있다면 작은 풍선을 터트려야 마지막까지 남게 됨

- 한번은 작은 풍선을 터트릴 수 있으므로 양 끝 인덱스의 풍선은 남을 수 있는 풍선 

즉, 양 방향으로 나보다 작은 수가 있는 경우에는 마지막까지 남을 수 없는 풍선

 

2) 양 방향에 나보다 작은 수가 있는지 판별

- 각 방향의 끝부터 현재 인덱스까지의 최소 값을 배열에 저장

 -> 현재 탐색 대상인 풍선의 인덱스와 위에 구했던 각 방향까지의 최소 값이 같다면 나보다 작은 풍선은 내가 됨 ( 해당 방향에 나보다 작은 풍선이 없음 )

 

주석 참조

    using System;

    public class Solution
    {
        public int solution(int[] a)
        {
            int answer = 2; // 양쪽 끝 인덱스는 무조건 최후의 풍선이 될 수 있음
            var left = new int[a.Length]; // 왼쪽 끝부터 인덱스번호까지의 최소 값을 담은 배열
            var right = new int[a.Length]; // 오른쪽 끝부터 인덱스번호까지의 최소 값을 담은 배열

            // left 배열 최소 값 세팅
            left[0] = a[0];
            for (int i = 1; i < a.Length; i++)
                left[i] = Math.Min(left[i - 1], a[i]);

            // right 배열 최소 값 세팅
            right[a.Length - 1] = a[a.Length - 1];
            for (int i = a.Length - 2; i >= 0; i--)
                right[i] = Math.Min(right[i + 1], a[i]);

            // 한쪽이라도 내가 최소 값이라면 최후의 풍선이 될 수 있음
            for (int i = 1; i < a.Length - 1; i++)
                if (a[i] == left[i] || a[i] == right[i])
                    answer++;

            return answer;
        }
    }