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

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

프로그래머스

 

2023.08.01 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건은 다음과 같습니다.

• 임의의 인접한 두 풍선을 고른다.
• 번호가 더 큰 풍선을 터트린다.
• 단 1번은 번호가 더 작은 풍선을 터트릴 수 있다. (찬스라고 하겠습니다!)

우선 무조건 번호가 더 큰 풍선을 터트려야 한다는 기조로 아이디어를 떠올렸습니다.

이렇게 하면 번호가 작은 풍선만 살아남게 됩니다.

 

 

입출력 예시

0	1	2	3	4	5	6	7	8	9
-16	27	65	-2	58	-92	-71	-68	-61	-33

위의 입출력 예시의 답은 6이라고 문제에서 제공하고 있습니다.

이 예시를 바탕으로 아이디어를 도출한 과정을 적어보겠습니다.

 

우선 0번째 아이템인 -16이 답에 포함될 수 있는지 생각해봅니다.

번호가 작은 풍선이 살아남기 때문에 5번째 아이템인 -92가 임의로 선택된 두 풍선중에 하나로 계속 선택된다면 결국 [-16, -92]만 남게 됩니다.

이 때, 찬스를 사용하여 큰 수인 -16을 선택한다면 최종적으로 -16이 살아남는 풍선이 되게 됩니다. ➡️ 정답에 포함

 

1번째 아이템인 27을 보겠습니다.

마찬가지로 -92가 다른 풍선들을 다 터트려주고 [-16, 27, -92]만 남게 될 수 있습니다.

이때, 27은 찬스를 사용하여 -92를 터트리게 되면 [-16, 27]이 남게 되고 27은 -16보다 크기 때문에 제거됩니다. ➡️ 정답에 포함 불가

-16과 27의 대결에서 찬스를 사용해도 [27, -92]가 남게되고 27은 -92보다 크기 때문에 제거됩니다. ➡️ 정답에 포함 불가

 

여기서 규칙을 찾을 수 있습니다.

 

i번째 인덱스의 풍선이 정답에 포함되려면 i의 좌측 부분의 풍선들의 최솟값인 leftMin과 오른쪽 부분의 풍선들의 최솟값인 rightMin보다 큰 수이면 안됩니다!

27의 사례에서 leftMin은 -16이고 rightMin은 -92였습니다. 27이 leftMin과 rightMin 둘 보다 컸기 때문에 마지막 결투에서 패배하고 터질 수 밖게 없는 것입니다!

 

만약 leftMin과 rightMin 중에서 하나라도 자신보다 큰 수가 있다면 정답이 될 수 있습니다.

왜냐하면 큰 수와의 비교에서는 작은 풍선이 살아남기 때문에 마지막 2개만 남은 상황에서 찬스를 사용하면 되기 때문입니다!

 

 

이제 중요한 것은 각 인덱스에서의 좌측과 우측의 최솟값을 찾는 것입니다.

a의 길이가 1,000,000개까지 가능하기 때문에 매번 최솟값을 찾는 것은 비효율적입니다. (시간 초과 발생)

 

따라서 미리 a를 순회하며 각 인덱스에 해당하는 최솟값을 찾아서 어레이에 저장해두는 방식을 사용했습니다. (DP 개념)

leftMin 배열과 rightMin 배열을 만들고 leftMin[i] 는 i번째 인덱스에서 좌측 풍선들의 최솟값을 의미합니다.

마찬가지로 rightMin[i]는 i번째 인덱스에서 우측 풍선들의 최솟값입니다.

 

 

풀이

fileprivate func solution(_ a:[Int]) -> Int {
    // 자신보다 큰 수가 왼쪽 또는 오른쪽의 최솟값으로서 존재하면 가능
    var result = 0
    var leftMin = Array(repeating: 1_000_000_000, count: a.count)   // 각 인덱스를 기준으로 왼쪽 부분의 최솟값을 저장
    var rightMin = Array(repeating: 1_000_000_000, count: a.count)  // 각 인덱스를 기준으로 오른쪽 부분의 최솟값을 저장
    
    for i in 1..<a.count {
        leftMin[i] = min(leftMin[i-1], a[i-1])
    }
    
    for i in stride(from: a.count-2, through: 0, by: -1) {
        rightMin[i] = min(rightMin[i+1], a[i+1])
    }
    
    for i in a.indices {
        let cur = a[i]
        
        let leftMinNum = leftMin[i]
        let rightMinNum = rightMin[i]
        
        if cur < leftMinNum || cur < rightMinNum {
            result += 1
        }
    }
    
    return result
}

총 3번 a를 순회하게 됩니다. ➡️ O(3*N)

O(N^2)에 비해 훨씬 빠른 로직입니다.

 

leftMin[i] = min(leftMin[i-1], a[i-1]) 은 i-1 위치까지의 최솟값과 i-1 위치의 값을 비교하여 더 작은 값을 i까지의 최솟값으로 설정하는 코드입니다.

 

rightMin도 같은 로직이지만 stride를 활용하여 어레이의 뒤부터 순회합니다. (우측 최솟값을 찾아야 하므로)

 

좌측과 우측 최솟값 중에서 cur보다 큰 값이 하나라도 있으면 result를 증가시킵니다.

 

마무리

아이디어를 떠올리는 것이 중요했습니다.

처음에 막막할 때에는 입출력 예제를 보고 직접 머릿속으로 비교하며 규칙을 찾는 것도 좋은 방법 중에 하나라고 생각합니다!

이번에도 입출력 예에서 직접 숫자들을 비교하다보니 좌측과 우측으로 나누어야 한다는 아이디어를 얻을 수 있었습니다!!

 

그 다음에는 좌측과 우측의 최솟값을 찾는 문제로 바뀌었습니다.

이때 매번 최솟값을 순회하며 찾으면 시간 초과가 발생하니까 미리 한번 쭉 순회하며 최솟값을 찾아서 저장해두는 방식을 사용했습니다.

이러한 방식도 몇번 사용해보면서 익숙해지면 유사한 문제가 나왔을 때 곧바로 떠올릴 수 있을 것 같습니다!!