[Swift] 프로그래머스 월간 코드 챌린지 시즌1 풍선 터뜨리기

 

 

Problem

 

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

---

Solution

 

이 문제의 핵심은 어떤 풍선이 절대로 터뜨릴 수 없는 풍선인가입니다.

 

규칙을 간단히 설명드리면 인접한 두 풍선을 골라서 터뜨리는데 자신보다 숫자가 큰 풍선은 마음대로 터뜨릴 수 있지만

 

자기보다 숫자가 작은 풍선은 딱 1번만 터뜨릴 수 있습니다.

 

고로 절대로 터뜨릴 수 없는 풍선은 터뜨리는 풍선의 기준에서 왼쪽의 수들 중 가장 작은 수가 현재 터뜨리려고 하는 풍선보다 크고

 

터뜨리는 풍선의 기준에서 오른쪽 수들 중 가장 작은 수가 현재 터뜨리려고 하는 풍선보다 큰 경우입니다.

 

즉, 현재 풍선 기준 왼쪽과 오른쪽의 가장 작은 수 2개가 모두 현재 풍선보다 큰 경우입니다.

 

이 규칙을 이해했다면 이제 효율적으로 문제를 풀어야 할 것입니다.

 

효율적으로 문제를 풀기 위해선 O(n) 의 시간복잡도로 풀 수 있는데요.

 

주어진 배열을 예시로 설명드리겠습니다. [-16,27,65,-2,58,-92,-71,-68,-61,-33] 

 

1. 가장 왼쪽의 수와 가장 오른쪽의 수를 정합니다. -> 가장 왼쪽 -16 가장 오른쪽 -33

 

2. 가장 왼쪽의 수와 가장 오른쪽의 수를 비교하여 더 큰 수쪽으로 방향을 정합니다. -> 왼쪽

 

3. 정해진 방향의 바로 옆의 수를 비교하여 옆의 수가 더 작다면 터뜨릴 수 있는 풍선이고 더 크다면 터뜨릴 수 없는 풍선입니다.

-> -16과 27 27이 더 크므로 27은 터뜨릴 수 없는 풍선입니다.

 

4. 현재 풍선과 옆의 풍선의 크기를 비교해 더 작은 수로 대체해줍니다. -> -16 과 27 중 더 작은 수는 -16이므로 왼쪽 수는 그대로 -16이 됩니다.

 

5. 다시 2번부터 반복해줍니다.

 

6. 이런식으로 모든 풍선을 비교해 터뜨릴 수 있는 풍선의 갯수를 세어 반환합니다. -> -16, -92, -71, -68, -61, -33

---

 

Source Code

 

---

P.S

처음 문제풀 땐 이렇게 쉬운 문제가 3단계야...? 라는 생각이 들 정도로 간단하게 풀었다.

 

하지만 역시 효율성을 보는 문제였다... 

 

근데 효율성을 본다해도 조금 쉬운 문제였음.

 

이게 3단계에 있을 문제는 아닌거 같은데...

func solution(_ a:[Int]) -> Int {
    
    var count = 2
    
    if a.count == 1{
        return 1
    }
    
    for i in 1..<a.count - 1 {
        
        let left = a[0...i-1]
        let right = a[i+1...a.count-1]
        let leftMin = left.min()
        let rightMin = right.min()
        
        if leftMin! < a[i] && rightMin! < a[i] {
            continue
        }
        
        count += 1
        
    }
    
    return count
}