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

programmers.co.kr/learn/courses/30/lessons/68646

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

 

풀이과정

문제

이웃된 값들중 큰값이 삭제

단 한번만 작은값을 삭제할 수 있고

삭제되지않는 풍선의 수를 구해라

 

현재 비교하려는 값이 삭제되지않는 경우

-> 어찌햇던 마지막에 양옆을 비교했을때 그 양옆의 수보다 작아야함 (셋중에 젤 작아야 남길수 있음)

x번째를 남기고싶다면

[0..<x]의 최솟값과 [x+1..<end]의 최솟값이 x번째 수보다 모두 작으면 x번째가 삭제당하므로 안됌

(하나만 작으면 한번 작은값을 삭제할 수 있어서 남길수 있음)

 

 

처음 접근방법
배열을 순회하면서 다음이 더 크다면 삭제하고
남은배열에 내가 확인하려는 숫자보다 양옆의 숫자가 작다면
남길수 없는 풍선임을 이용
작은경우는 최대1번만 허용이기 때문

-> 시간초과 n^2이상.. 실패... 

두번째
현재 확인하려는 숫자보다 양옆 최솟값이 작으면안됌

배열을 순회하면서 최솟값을 비교
최솟값비교 n, 배열 비교 n -> n^2 실패...

 

마지막
현재 확인숫자 기준으로 왼쪽최솟값과 오른쪽 최솟값을 비교해서 그 둘보다 커야함
n^2으론 절대 불가능하니 n으로 해야했고(1,000,000^2 시간초과)
배열을 만들어서
왼쪽부터 비교한 최솟값
오른쪽부터 비교한 최솟값을 만들고
현재 값과 왼쪽최솟값, 오른쪽최솟값을 비교하는 로직으로 해결
3n

 

private func solutionP68646(_ a:[Int]) -> Int {
    
    if a.count < 3 {
        return a.count
    }
    
    var result = 0
    var minNum = Int.max
    var leftMins: [Int] = []
    var rightMins: [Int]
    
    for i in 0..<a.count {
        if minNum > a[i] {
            minNum = a[i]
        }
        leftMins.append(minNum)
    }
    
    rightMins = [Int](repeating: 0, count: leftMins.count)
    minNum = Int.max
    for i in stride(from: a.count-1, through: 0, by: -1) {
        if minNum > a[i] {
            minNum = a[i]
        }
        rightMins[i] = minNum
    }
    
    for i in 0..<a.count {
        if leftMins[i] < a[i] && rightMins[i] < a[i] {
            continue
        }
        result += 1
    }
    
    return result
}