[Swift 알고리즘] 백준 6198 - 옥상 정원 꾸미기

안녕하세요 코코종입니다~

프로그래머스 3단계를 쬐금 풀다가 벽을 느끼고....(+면접이다 뭐다 바쁘게 보냈네요)

백준에서 문제를 좀 풀어보기로 결정했습니다!

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

6198번: 옥상 정원 꾸미기

 

import Foundation

let n = Int(readLine()!)!
var data : [Int] = []

var answer = 0

for _ in (0..<n) {
    data.append(Int(readLine()!)!)
}



// 하나하나 해본다면 -> 시간초과
//for i in (0..<n-1) { // 기준
//    for j in (i+1..<n) { // 오른쪽(i+1 부터 n-1까지)
//        if data[i] > data[j] {
//            result += 1
//        } else {
//            break
//        }
//
//    }
//}

var stack: [Int] = []

for i in (0...n-1) {
    while stack.count != 0 && stack.last! <= data[i] {
        stack.removeLast()
    }
    
    stack.append(data[i])
    answer += stack.count - 1
    
}

print(answer)

 

---

 

처음에 난이도를 보고 이게 왜 골드..? 라고 하면서 무지성 구현을 했더니

최악의 경우 O(n^2)가 되어버리는 바람에 시간초과가 뜨더라구요. 역시 그러면 그렇지.. 하면서 고민을 했는데

옛날에 공부했던 '가장 긴 증가하는 수열'이 생각나서 DP로 푸는건가? 싶다가 슬쩍 문제 유형을 컨닝했는데 스텍이어서 스텍으로 돌렸습니다 ㅋㅋㅋ 스텍을 보고 나니 좀 수월하게 풀었습니다.

 

간단하게 설명을 하면 스텍의 가장 위에 있는 값(stack.last)보다 현재의 높이가 크거나 같은 값이라면 stack에서 제거를 해줍니다. (그렇게 되면 더 작은 건물만 남겠죠?) 그 후 내 건물을 넣어주는 식으로 했습니다. 내 건물은 참고할 수 없으므로 stack의 크기에서 -1 해준 값을 더해줬습니다.

 

사실 처음에는 저거보다 코드가 좀 더러웠는데 (count 가 0 이라면, 아니라면 등등) 다른분들의 코드를 참고하고 좀 간단하게 줄일 수 있었습니다. (존경합니다...)

풀고 아직 블로그에 올리지 못 한 2문제가 있긴 한데... 오늘은 이만! 물러가겠습니다~~