728x90
> 파이썬, 자료 구조, 스택
📖 문제 : 스카이라인 쉬운거 (Python)
도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.
정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.
출력
첫 줄에 최소 건물 개수를 출력한다.
예제 입력 1
10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
예제 출력 1
6
내 코드
N = int(input())
buildings = []
result = 0
for _ in range(N):
x, y = map(int, input().split())
if y == 0:
result += len(buildings)
buildings = []
else:
if len(buildings) == 0:
buildings.append(y)
else:
while len(buildings) > 0 and buildings[-1] > y:
buildings.pop()
result += 1
if len(buildings) > 0 and buildings[-1] == y:
continue
else:
buildings.append(y)
print(len(buildings) + result)
Point ! ⭐️
- 이 문제의 예제 1번을 보고는
0이 나오면 리스트를 비워주고, 그게 아니라면 그 리스트에 모든 수를 다 넣어서 set (집합)의 길이를 결과값에 계속 더해주는 방법을 생각해서 구현하니 7%에서 틀리더라구요
하지만 ! 반례가 있다는 것
4
1 4
2 3
3 5
4 4
의 경우 건물의 높이를 보면
4 3 5 4 이렇게 되는데 저의 처음 방법대로라면 결과값이 3이 나오지만, 나와야하는 값은 4 입니다.
왜냐하면, 위치 1과 4의 4높이의 건물이 하나의 건물이라고 생각하면 2위치에 있는 3높이의 건물은 보이지 않을 것입니다.
그러므로 위치 1과 4의 건물은 각각 하나씩 총 2개의 건물이라고 생각해야하기 때문에 총 4개의 건물이 되는 것입니다.
이 반례를 토대로 저는 stack 을 사용하여 구현하였습니다.
stack 쌓이는 기준은 기존 stack 안에 있는 수보다 무조건 커야 그 스택에 들어갈 수 있으며
들어오는 수가 스택의 가장 위의 수보다 작으면 기존 스택에 있는 수를 들어오는 수보다 작을 때까지 pop 해주면서 결과값에 +1씩 해줍니다. 그러곤 마지막에 스택에 남아있는 수들의 갯수와 합해 결과값에 더하여 출력합니다.
참고로 들어오는 수와 스택의 가장 위의 수와 값이 같을 경우는,
그냥 스택에 들어오는 수를 넣지 않습니다.
백준
https://www.acmicpc.net/problem/1863
728x90
'Algorithm (Python, Java, SQL) > BaekJoon' 카테고리의 다른 글
[백준 21921번] 블로그 (Python) (1) | 2023.11.13 |
---|---|
[백준 1515번] 수 이어쓰기 (Python) (1) | 2023.11.13 |
[백준 2636번] 치즈 (Python) (0) | 2023.10.24 |
[백준 2870번] 수학숙제 (Python) (0) | 2023.10.24 |
[백준 17144번] 미세먼지 안녕 !(Python) (2) | 2023.10.24 |