[백준(BOJ)] 1863 스카이라인 쉬운거 - 스위프트(Swift)

[Gold IV] 스카이라인 쉬운거 - 1863

문제 링크

성능 요약

메모리: 79648 KB, 시간: 24 ms

분류

자료 구조, 스택

문제 설명

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

출력

첫 줄에 최소 건물 개수를 출력한다.

 

풀이

해당 예제는 다음과 같은 스카이라인을 나타냅니다.

// 입력값
10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1




// 입력값 표시
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX



// 결과
6

처음에 입력값 표시와 결과를 보고 무슨 소리인가 했는데 건물들이 Z축으로 쌓여있다고 생각하시면 될 것 같습니다.

 

 

이 문제에서 생각해야하는 것은 "y좌표가 낮아지는 지점에서 건물을 세는 것"입니다.

y좌표가 낮아졌다면 해당 지점에서 어떠한 건물이 끝났다는 것을 의미하기 때문입니다.

 

하지만 여기서 주의해야 할 점이 있습니다.

y좌표가 낮아지면서 한 번에 두 개 이상의 건물이 끝나는 경우입니다.

 

따라서 값들을 스택에 저장해두고 만약 y좌표가 낮아졌다면 해당 값들을 모두 스택에서 빼주면 됩니다.

 

다음은 코드입니다.

import Foundation

// 입력 받기
let n = Int(readLine()!)! // 건물의 개수를 입력 받음
var answer = 0 // 필요한 건물의 개수를 저장할 변수

var skylines = [Int]() // 건물의 높이를 저장할 배열

// 각 건물의 위치와 높이를 입력 받아 배열에 저장
for _ in 0..<n {
    skylines.append(Int(readLine()!.split(separator: " ")[1])!)
}

skylines.append(0) // 스카이라인의 마지막 높이를 0으로 설정

var stack = [0] // 스택을 초기화하고 0으로 시작

for p in skylines {
    var height = p // 현재 건물의 높이
    while stack.last! > p {
        // 스택의 마지막 요소가 현재 건물의 높이보다 큰 경우
        if stack.last! != height {
            // 스택의 마지막 요소가 현재 건물의 높이와 다르면
            answer += 1 // 필요한 건물 개수를 증가
            height = stack.last! // 현재 높이를 스택의 마지막 높이로 업데이트
        }
        stack.removeLast() // 스택에서 요소 제거
    }
    stack.append(p) // 현재 건물의 높이를 스택에 추가
}

print(answer) // 필요한 건물의 개수 출력