문제 바로가기
문제:
도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다. 정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.
입력:
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.
출력:
첫 줄에 최소 건물 개수를 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input()) # 건물의 개수 입력
lst = [int(sys.stdin.readline().split()[1]) for i in range(n)] # 건물의 높이를 리스트에 저장
lst.append(0) # 스택 연산을 위한 초기 설정: 높이가 0인 가상의 건물 추가
stk = [0] # 높이를 저장하는 스택 초기화
res = 0 # 도시에 세워진 건물의 개수 초기화
for i in lst: # 건물 리스트 순회
now = i # 현재 건물의 높이
while stk[-1] > i: # 스택의 마지막 원소가 현재 높이보다 큰 경우 반복
if stk[-1] != now: # 스택의 마지막 원소가 이전 건물의 높이와 다른 경우
res += 1 # 새로운 건물의 시작을 의미하므로 건물 개수 증가
now = stk[-1] # 현재 건물의 높이를 스택의 마지막 원소로 갱신
stk.pop() # 스택의 마지막 원소 제거
stk.append(i) # 현재 건물의 높이를 스택에 추가
print(res) # 도시에 세워진 건물의 개수 출력
이 문제는 스택을 이용한 문제이다.
잘 보면 높이가 낮아 질때 그 건물이 끝이난다. 건물의 높이만을 가져와서 리스트에 저장한다.
그래서 시작위치인 0 을 stk에 넣어준다.
건물의 리스트를 돌면서
현재 건물의 높이를 저장해 놓아야지. 스택을 돌리면서 한번에 여러개 건물이 끝날 지점을 체크하기 위해 필요하다.
예를들면 2층 3층 1층 이렇게 되면 2층 3층 짜리 건물 둘다 끝나는거로 체크하기 위해서이다.
stack = [] # 건물의 높이
cnt = 0
for i in range(n): # 건물의 개수만큼 반복
nums = list(map(int, input().split())) # 건물의 번호와 높이 입력 받음
while stack: # 스택이 비어있지 않은 동안 반복
if stack[-1] > nums[1]: # 스택의 마지막 원소가 현재 건물의 높이보다 큰 경우
cnt += 1 # 새로운 건물의 시작을 의미하므로 건물 개수 증가
stack.pop() # 스택의 마지막 원소 제거
elif stack[-1] == nums[1]: # 스택의 마지막 원소가 현재 건물의 높이와 같은 경우
stack.pop() # 스택의 마지막 원소 제거
else:
break # 스택의 마지막 원소가 현재 건물의 높이보다 작은 경우 반복 중단
stack.append(nums[1]) # 현재 건물의 높이를 스택에 추가
while stack: # 스택에 남아있는 건물들을 처리
new = stack.pop()
if new >= 1: # 높이가 1 이상인 경우
cnt += 1 # 건물 개수 증가
print(cnt) # 도시에 세워진 건물의 개수 출력비슷한 방법이 있다. 건물을 하나 돌때마다 건물을 추가 해 주면서 스택을 비교하는 방법이다.
건물 개수만큼 반복 한 후에 남아 있는 스택도 확인을 해줘야 한다.
이것도 똑같이 건물의 높이가 낮아지면 건물이 1개 완성되는것이다.
예를들면
높이가 1,2,1,3 이면
----
----- (1개) ---- (2개)
--------------------------- (3개)
이런식으로 된다.
댓글