반응형
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
}
반응형
'iyOmSd > Title: Algorithm풀이' 카테고리의 다른 글
[Swift Algorithm] 프로그래머스 49189 가장 먼 노드 (0) | 2020.12.11 |
---|---|
[Swift Algorithm] 프로그래머스 60059 자물쇠와 열쇠 (2020 카카오 블라인드) (2) | 2020.11.30 |
[Swift Algorithm] 프로그래머스 17676 추석 트래픽 (2018 카카오 블라인드) (0) | 2020.11.18 |
[Swift Algorithm] 프로그래머스 17687 N진수 게임 (2018 카카오 블라인드) (0) | 2020.11.14 |
[Swift Algorithm] 프로그래머스 17683 방금 그곡 (2018 카카오 블라인드) (0) | 2020.10.29 |