[스택] 백준 - 1863번: 스카이라인 쉬운 거 (파이썬)

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

 

문제

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

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

입력

첫째 줄에 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

다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다.

..........................
.....22.........333.......
.111.22.......XX333XX.....
X111X22XXX....XX333XXXXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......5555555.....
4444444444....5555555XXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

 

---

새삼 내가 스택 응용 실력이 확실히 부족하구나 느끼게 해준 문제였다.

중간에 딴짓을 많이 하긴 했지만 ... ..... ... 끝까지 틀렸다고 나와서 스스로 채찍질을 하게 만듦,,

 

 

오답 코드

import sys

input = sys.stdin.readline

n = int(input())
crd = []
for _ in range(n):
    x, y = map(int, input().split())
    crd.append((x, y))

cnt = 0
stack = []

for i in range(n):
    x, y = crd[i]

    if not stack or stack[-1] < y:
        stack.append(y)
        if y != 0:
            cnt += 1

    if not stack or stack[-1] != y:
        stack.append(y)

    while stack and stack[-1] >= y:
        stack.pop()


print(cnt)

 

💢 문제가 되었던 부분

if not stack or stack[-1] < y:
    stack.append(y)
    if y != 0:
        cnt += 1

if not stack or stack[-1] != y:
    stack.append(y)

while stack and stack[-1] >= y:
    stack.pop()

• 스택이 비어 있거나 top의 값이 y가 아닐 때: 전제 조건이 잘못 되었던 것 같다. 다음에 다른 높이가 온다고 한들 그걸 비교하는 의미가 없었던 거 같음.
• 스택에 남아 있는 빌딩을 합산해서 카운팅하지 않았다.
• 높이가 바뀌는 지점만 따진 것 같다,,,,

 

매니저 님이 올려 주신 풀이를 참고해서 다시 풀이해 보았다.

정답 코드

import sys

input = sys.stdin.readline

n = int(input())
crd = []
for _ in range(n):
    x, y = map(int, input().split())
    crd.append((x, y))

cnt = 0
stack = []

for i in range(n):
    x, y = crd[i]

    if y == 0:
        cnt += len(stack)  # 스택에 남아 있는 빌딩들을 모두 하나의 빌딩으로 처리
        stack = []         # 스택을 비워 주고 다음 빌딩으로 이동
        continue

    while stack and stack[-1] > y:  # 스택이 비어 있지 않고, 스택의 top이 y보다 클 때
        stack.pop()
        cnt += 1

    if not stack or stack[-1] < y:  # 스택이 비어 있거나 스택의 top이 y보다 작을 때
        stack.append(y)

print(cnt + len(stack))  # 스택에 남아 있는 빌딩들을 하나의 빌딩으로 처리

 

수정한 조건

• 빌딩이 사라질 때
• 스택이 비어 있지 않고 top이 y보다 클 때
• 스택이 비어 있거나 top이 y보다 작을 때
• 스택에 남아 있는 빌딩을 모두 합산해서 처리

같은 높이의 스카이라인을 가지는 위치들은 한 빌딩으로 처리해야 한다.

이때 이 사이에 그 높이보다 낮은 스카이라인이 있다면 한 빌딩으로는 처리할 수 없다.

 

 

스택 문제를 더 많이 풀어 봐야 겠다..! 내가 그동안 쉬운 문제만 풀어왔구나,,하고 생각했던 하루였다.