문제 소개
해당 문제는 리스트 형태의 스카이라인이 주어졌을 때 건물이 최소 몇개인지 물어보는 문제이다. 문제에서 제공하는 예제를 아래의 배경에 보이고자 한다.
위와 같은 배경에 아래와 같이 스카이 라인이 그려진다.
주황색 칸에 직사각형 빌딩을 최소로 채우기 위해 아래의 그림과 같이 빌딩이 그려진다.
문제 분석
처음 문제를 봤을 때 반복문을 통해 2차원 좌표를 조건에 맞게 직사각형 빌딩을 그리고 방문처리를 통해 해결하고자 했다.
하지만 문제가 메모리 초과가 발생해서 문제의 x범위가 10^6이라 메모리 초과가 발생하였고 방문처리를 생략했음에도 불구하고 이번에는 시간초과가 발생하였다.
그리하여 이러한 방식은 잘못되었다고 판단하여 다시 생각해보았다.
스카이 라인의 고도(y)를 받을 때마다 전의 스카이라인보다 작으면 전의 스카이라인에 해당하는 영역이 최소 빌딩 조건을 충족하기 때문에, 빌딩이 만들어진다.
해결책 1(글쓴이)
정리하자면, 아래와 같다.
스카이 라인을 입력받음
1. 전 스카이 라인 고도보다 현재 스카이 라인 고도가 클 경우
2. 전 스카이 라인 고도보다 현재 스카이 라인 고도가 작을 경우
3. 전 스카이 라인 고도와 현재 스카이 라인 고도가 같을 경우
1번과 같은 경우에는 뒤의 스카이 라인 고도에 따라 빌딩의 성립 조건이 달라지 때문에 두고봐야하는 경우이다.
2번은 현재 스카이 라인 고도가 전 스카이 라인보다 작기 때문에 무조건 빌딩이 만들어진다.
3번과 같이 같을 경우에는 같은 빌딩으로 취급되기 때문에 패스해야한다.
위의 알고리즘을 적용하면 아래의 코드와 같다.
import sys
def solution():
global n
n = int(input().rstrip('\n'))
stack = []
ans = 0
for _ in range(n):
x, y = map(int, input().split())
while stack and stack[-1] > y:
stack.pop()
ans += 1
if stack and stack[-1] == y:
continue
if y > 0:
stack.append(y)
print(ans + len(stack))
input = sys.stdin.readline
solution()해결책 2
다른 사람의 코드를 보니 재밌는 부분이 있어 가져와보았다.
이 코드도 마찬가지로 핵심 알고리즘은 해결책1과 동일하게 스카이 라인이 낮아질때 빌딩을 카운팅한다. 하지만, 스카이 라인이 같을 경우 마지막으로 카운트한 건물의 높이를 기록해둬서 같은 높이일 경우 pop을 해준다.
해당 작성자분의 예시이다. stack의 진행사항은 아래와 같다.
- (1,1) 적용
stack : [(1,1)]- (2,2) 적용
stack : [(1,1),(2,2)]- (5,1) 적용
stack : [(1,1),(5,1)]- (6,3) 적용
stack : [(1,1),(5,1),(6,3)]- (8,1) 적용
stack : [(1,1),(5,1),(8,1)]- (11,0) 적용
stack : [(11,0)]
위의 6번째 단계에서 (11,0)이 주어졌고 먼저 (8,1)이 작기 때문에 pop된다. 이 때, (8,1)을 기록해뒀음으로 다음 (5,1)이 들어왔을 때 중복체크되지 않고 pop된다.
해당 코드는 아래의 링크로 가서 직접 보길 바란다.
