[Swift] 백준_옥상정원 꾸미기(6198)

문제

 

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

6198번: 옥상 정원 꾸미기

 

풀이

 

시간초과된거

 

처음에는 각 빌딩이 볼 수 있는 빌딩 수에 초점을 맞췄었다. 그래서 중첩된 반복문을 통해 현재의 빌딩보다 높이가 높은 빌딩들만 스택에 남겨 result[index]에 값을 매번 더해주었다. 시간복잡도가 O(n^2)이라 찝찝했지만 역시나 시간초과였다.

let n = Int(readLine()!)!
var result = Array(repeating: 0, count: n)
var stack: [Int] = []
var buildings: [Int] = []

for i in 0..<n {
    let height = Int(readLine()!)!
    buildings.append(height)
    while !stack.isEmpty && buildings[stack.last!] < buildings[i] {
        stack.removeLast()
    }
    for idx in stack {
        result[idx] += 1
    }
    stack.append(i)
}
print(result.reduce(0) { $0 + $1 })

주어진 예시를 통해 설명하자면,

먼저 높이가 10인 건물이 들어오는데, 스택이 비어있으므로 stack은 [0]이 되고, buildings는 [10]이 된다.

 

다음 건물은 높이가 3이므로 buildings[0]보다 작다. 따라서 stack에 들어있는 0번째 인덱스 건물이 볼 수 있는 건물 수에 1을 더해주게되어 result는 [1,0,0,0,0,0]이 되고, stack은 [0,1]이 된다.

 

다음 건물은 높이가 7이므로 buildings[stack.last!]인 3보다 크다. stack의 마지막 원소를 지우면 stack.last!는 10이되어 7보다 커진다. 따라서 stack은 [0]이 되므로 result는 [2,0,0,0,0,0]이 된다. 

 

이런식으로 계산을 하면 값이 나오지만 시간초과가 된다.

 

 

수정한거

 

각 빌딩이 볼 수 있는 빌딩의 수가 아닌 현재 빌딩을 볼 수 있는 빌딩의 수에 초점을 맞추었다.

위의 방법처럼 매번 반복문을 통해 각 빌딩이 볼 수 있는 빌딩 수를 늘려주는 것이 아닌, 현재 스택의 count를 이용하였다.

let n = Int(readLine()!)!
var result = 0
var stack: [Int] = []
var buildings: [Int] = []

for i in 0..<n {
    buildings.append(Int(readLine()!)!)
    while !stack.isEmpty && buildings[stack.last!] < buildings[i] {
        stack.removeLast()
    }
    result += stack.count
    stack.append(i)
}
print(result)

기존의 방법이랑 차이가 없다. 다만 초점을 바꿔서 계산하는 방법에 차이를 둔 것뿐이다. stack에는 현재 빌딩보다 큰 빌딩의 인덱스만 남아있으므로 단순히 stack의 count만 구해주면 된다.

 

 

_____________________________________________________________________________________________________

 

방향이 정해져있는 경우에는 한 번 스택을 이용할 수 있는지 생각해보자.