프로그래머스: 징검다리 건너기 Swift 풀이(재밌는 자료구조)
요새는 Swift로 프로그래머스 문제를 주에 3개씩 풀고 있는데
재밌는 자료구조를 발견해서 가져왔슴니다
징검다리 건너기
https://school.programmers.co.kr/learn/courses/30/lessons/64062
대충 각 디딤돌의 사용 가능한 횟수를 주고, k개는 디딤돌 없어도 건너뛸 수 있다고 할 때 얼마나 많이 건널 수 있을까?? 하는 문제
조건
- 배열 크기 20만 이하
- 각 값은 2억 이하
풀이1
import Foundation
func solution(_ stones:[Int], _ k:Int) -> Int {
var ans = Int.max
var r = k-1
while r < stones.count {
r += 1
// print(stones[r-k..<r])
ans = min(ans, stones[r-k..<r].max()!)
}
return ans
}
대충 k만큼 이어진 구간을 윈도우로 해서 거기서 max 값들의 min 값을 찾으면 안 되나?? 해서 해 봄
채점 결과(효율성 시간 초과)
정확성 테스트
테스트 1 〉 통과 (0.03ms, 16.5MB)
테스트 2 〉 통과 (0.05ms, 16.3MB)
테스트 3 〉 통과 (0.06ms, 16.4MB)
테스트 4 〉 통과 (0.11ms, 16.6MB)
테스트 5 〉 통과 (0.08ms, 16.5MB)
테스트 6 〉 통과 (0.57ms, 16.5MB)
테스트 7 〉 통과 (3.76ms, 16.4MB)
테스트 8 〉 통과 (5.18ms, 16.5MB)
테스트 9 〉 통과 (9.38ms, 16.4MB)
테스트 10 〉 통과 (0.13ms, 16.5MB)
테스트 11 〉 통과 (0.06ms, 16.4MB)
테스트 12 〉 통과 (0.06ms, 16.1MB)
테스트 13 〉 통과 (0.09ms, 16.3MB)
테스트 14 〉 통과 (0.56ms, 16.4MB)
테스트 15 〉 통과 (3.50ms, 16.4MB)
테스트 16 〉 통과 (4.62ms, 16.2MB)
테스트 17 〉 통과 (8.88ms, 16.3MB)
테스트 18 〉 통과 (0.04ms, 16.3MB)
테스트 19 〉 통과 (0.11ms, 16.3MB)
테스트 20 〉 통과 (0.09ms, 16.2MB)
테스트 21 〉 통과 (0.60ms, 16.4MB)
테스트 22 〉 통과 (2.49ms, 16.4MB)
테스트 23 〉 통과 (5.52ms, 16.4MB)
테스트 24 〉 통과 (10.29ms, 16.2MB)
테스트 25 〉 통과 (0.05ms, 16.3MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)
논리는 맞긴 하네
복잡도는 (n-k) 순회, k개에서 max 찾기 해서 $O((n-k)k)$인데 시간 초과 남
k = n/2 일 때 최댓값이니까 $O(n^2/4)$
풀이2
위 풀이에서 매번 k개 중의 최댓값 구하는 게 문제인데…
그럼 큐 형태면서 최댓값 빠르게 구할 수 있는 거 없나? 뭔가 저장해 놓으면 어째 될 거 같은데… 싶어서 찾아 봄
그리고 스택 오버플로우에 누가 올린 정확히 똑같은 문제를 찾았슴니다 -> 어느 아마존의 인터뷰 문제
해당 기능을 위한 자료구조 설명은 여기 -> push, pop, getMin이 상수인 자료구조
class MaxQueue {
private var pushStack: [(val: Int, maxVal: Int)] = []
private var popStack: [(val: Int, maxVal: Int)] = []
func push(_ val: Int) {
var maxVal = val
if !pushStack.isEmpty {
maxVal = max(maxVal, pushStack.last!.maxVal)
}
pushStack.append((val: val, maxVal: maxVal))
}
func pop() -> Int? {
if popStack.isEmpty {
if pushStack.isEmpty {
return nil
} else {
var val = pushStack.popLast()!.val
popStack.append((val: val, maxVal: val))
while !pushStack.isEmpty {
val = pushStack.popLast()!.val
let maxVal = max(popStack.last!.maxVal, val)
popStack.append((val: val, maxVal: maxVal))
}
}
}
return popStack.popLast()!.val
}
func getMax() -> Int? {
if pushStack.isEmpty {
if popStack.isEmpty {
return nil
} else {
return popStack.last!.maxVal
}
} else if popStack.isEmpty {
return pushStack.last!.maxVal
} else {
return max(pushStack.last!.maxVal, popStack.last!.maxVal)
}
}
}
재밋네요…
일단 스택 2개로 큐 구현하고
각 스택은 자기 값과 현재 맥스 값을 튜플로 가집니다
푸시할 땐
- pushStack이 있다면 pushStack의 max를 max로 하여 넣기
팝할 땐
- popStack, pushStack 모두 비었다면 없는 거니까 nil
- popStack이 비었다면
- pushStack에서 꺼내서 popStack으로 옮기기(maxVal은 val로, 나중에 생각해 보면 push가 비었을 때 getMax하면 얘가 마지막에 팝될 애이므로 해당 구간에선 자기가 최고일 거고, push가 있을 땐 둘이 비교해서 max 리턴하면 되니까)
- 그리고 빌 때까지 계속 꺼내서 popStack의 maxVal과 비교하여 자신의 maxVal 정하고 popStack에 다시 넣기
- 이제 popStack이 있으니 마지막 걸 꺼내 주기
전부 amortized $O(1)$이라네요
이게 뭔 소리야?! pop할 때 다 옮기고 난리 났구만 뭔 O(1) 싶으시다면 아래 설명을 읽어 주세요
amortized
제일 많이 드는 예는 C++의 벡터에 push_back() 입니다
벡터가 일단 capacity만큼 자리 차지 하고, 거기서 넘어가면 크기가 2배인 곳에다가 옮기잖아요
근데 생각해보면 이거 다 옮겨 버리는데 시간 복잡도 최악의 경우엔 사실 $O(n)$아님?? 싶은데
저런 경우가 어쩌다 한 번밖에 안 나오니까 이걸 계산을 해 보면은
평소에는 $O(1)$로 하다가 마지막 딱 한 번만 옮겨야 해서 $O(n)$이면 사실상 $\frac{O(1) * (n-1) + O(n) * 1}{n}$ 해서 $O(1)$이나 마찬가지인 거임!!
위 자료구조도 마찬가지로 popStack이 비었을 때에만 pushStack을 popStack 쪽으로 옮기고, 평상시에는 옮겨 뒀던 거 쓰면 되니까 사실상 평균 내면 거의 $O(1)$이라 봐도 된다는 뜻임니다
import Foundation
func solution(_ stones:[Int], _ k:Int) -> Int {
var ans = Int.max
var window = MaxQueue()
stones[0..<k-1].forEach { window.push($0) }
var r = k-1
while r < stones.count {
window.push(stones[r])
r += 1
ans = min(ans, window.getMax()!)
window.pop()
}
return ans
}
해당 자료구조 써서 넣고 빼고 맥스 비교 해보면
채점 결과(통과)
정확성 테스트
테스트 1 〉 통과 (0.06ms, 16.6MB)
테스트 2 〉 통과 (0.06ms, 16.3MB)
테스트 3 〉 통과 (0.11ms, 16.3MB)
테스트 4 〉 통과 (0.10ms, 16.4MB)
테스트 5 〉 통과 (0.24ms, 16.4MB)
테스트 6 〉 통과 (0.55ms, 16.5MB)
테스트 7 〉 통과 (1.57ms, 16.6MB)
테스트 8 〉 통과 (1.11ms, 16.3MB)
테스트 9 〉 통과 (1.33ms, 16.3MB)
테스트 10 〉 통과 (0.24ms, 16.3MB)
테스트 11 〉 통과 (0.14ms, 16.5MB)
테스트 12 〉 통과 (0.11ms, 16.4MB)
테스트 13 〉 통과 (0.25ms, 16.4MB)
테스트 14 〉 통과 (0.80ms, 16.6MB)
테스트 15 〉 통과 (1.27ms, 16.5MB)
테스트 16 〉 통과 (1.90ms, 16.6MB)
테스트 17 〉 통과 (1.90ms, 16.5MB)
테스트 18 〉 통과 (0.11ms, 16.2MB)
테스트 19 〉 통과 (0.11ms, 16.4MB)
테스트 20 〉 통과 (0.16ms, 16.4MB)
테스트 21 〉 통과 (0.64ms, 16.3MB)
테스트 22 〉 통과 (2.06ms, 16.7MB)
테스트 23 〉 통과 (1.08ms, 16.2MB)
테스트 24 〉 통과 (1.12ms, 16.6MB)
테스트 25 〉 통과 (0.09ms, 16.6MB)
효율성 테스트
테스트 1 〉 통과 (194.50ms, 25.6MB)
테스트 2 〉 통과 (212.44ms, 25.7MB)
테스트 3 〉 통과 (211.92ms, 25.7MB)
테스트 4 〉 통과 (213.86ms, 25.6MB)
테스트 5 〉 통과 (211.39ms, 25.5MB)
테스트 6 〉 통과 (202.16ms, 25.5MB)
테스트 7 〉 통과 (193.14ms, 25.4MB)
테스트 8 〉 통과 (164.61ms, 28.5MB)
테스트 9 〉 통과 (168.79ms, 25.3MB)
테스트 10 〉 통과 (143.84ms, 28.6MB)
테스트 11 〉 통과 (167.61ms, 25.8MB)
테스트 12 〉 통과 (134.08ms, 28.6MB)
테스트 13 〉 통과 (192.35ms, 25.6MB)
테스트 14 〉 통과 (178.66ms, 25.7MB)
성공~~
$O(n-k)$와 amortized $O(1)$ 입니다
와… 이렇게 수준 높은 문제를 낸다고? 싶었는데(위 스택 오버플로우에서도 아마존에서 이상한 문제 냈다고 누가 뭐라 함)
이거 사실 거의 이분탐색으로 푼다네요
이분탐색 풀이는 구글링 해서 다른 분들 거 보셔요 저는 이분탐색으로 다시 풀어보러 가겟슴니다…
댓글남기기