[Swift] 백준_오아시스 재결합

문제

 

https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

 

 

풀이

 

처음에는 스택에 계속 추가하다가 last값보다 새로 들어오는 값이 더 큰 경우에만 removeLast()를 하도록했다. 그러다보니 중복된 경우가 있는 상태에서 해당 값보다 큰 값이 들어올때마다 중복되는 개수만큼 반복문을 돌게되었다. 역시 시간초과

 

 

두번째로 했던 방법에서는 스택에 키만 갖는 원소를 추가하는 것이 아닌, 높이와 개수를 갖는 [Int]를 추가하도록 해주었다.

 

새로 들어오는 원소 person을 [키, 1]로 초기화하고, 스택의 마지막 원소의 키보다 person의 키가 큰 경우에는 person 이후의 사람과 어차피 볼 수 없으므로 removeLast()를 통해 스택에서 제거하였다.

 

이때, 키가 같은 경우에는 스택의 마지막 원소를 제거하고 person의 count를 제거된 원소의 count만큼 증가시키고 마지막에 스택에 person을 스택에 다시 추가하여 count만 올라가도록 하였다.

 

그리고 만약 반복문을 돈 후에 스택이 비어있지 않다면 person의 키보다 큰 원소가 있다는 얘기이고, 그 원소보다 큰 원소는 어차피 볼 수 없으니 result에 1만 추가해주었다.

import Foundation

let n = Int(readLine()!)!
var stack: [[Int]] = [] //0은 높이, 1은 개수(중복체크)
var result: Int = 0
for _ in 0..<n {
    var person = [Int(readLine()!)!, 1]
    while !stack.isEmpty && stack.last![0] <= person[0] {
        result += stack.last![1]
        if stack.last![0] == person[0] {
            person[1] += stack.last![1]
        }
        stack.removeLast()
    }
    if !stack.isEmpty {
        result += 1
    }
    stack.append(person)
}
print(result)

 

_____________________________________________________________________________________________________

 

스택 문제는 푸는 방식이 얼추 비슷한 느낌

 

https://please-amend.tistory.com/16 를 참고함.