[WEEK02] 정글시험 1933 스카이라인

문제

N개의 직사각형 모양의 건물들이 주어졌을 때, 스카이라인을 구해내는 프로그램을 작성하시오. 스카이라인은 건물 전체의 윤곽을 의미한다. 즉, 각각의 건물을 직사각형으로 표현했을 때, 그러한 직사각형들의 합집합을 구하는 문제이다.

예를 들어 직사각형 모양의 건물들이 위와 같이 주어졌다고 하자. 각각의 건물은 왼쪽 x좌표와 오른쪽 x좌표, 그리고 높이로 나타난다. 모든 건물들은 편의상 같은 높이의 지면(땅) 위에 있다고 가정하자. 위의 예에서 스카이라인을 구하면 아래와 같다.

입력

첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오른쪽 x좌표를 의미한다. (1 ≤ L < R ≤ 1,000,000,000, 1 ≤ H ≤ 1,000,000,000)

출력

첫째 줄에 스카이라인을 출력한다. 출력을 할 때에는 높이가 변하는 지점에 대해서, 그 지점의 x좌표와 그 지점에서의 높이를 출력한다.

풀이

처음에는 어떻게 풀지 감이 잡히지 않아 오로지 조건으로만 검사해서 출력을 해주었고 그 때의 코드는 다음과 같다.

실패코드

import sys

n = int(input())
stack = []
coordis = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
coordis.sort()

for i in range(len(coordis)):
    if stack:
        if stack[-1][1] > coordis[i][1]:
            if coordis[i][2] <= stack[-1][2]:
                continue
            elif coordis[i][0] <= stack[-1][2]:
                coordis[i][0] = stack[-1][2]
                stack.append(coordis[i])
            else:
                stack.append(coordis[i])
        elif stack[-1][1] < coordis[i][1]:
            if stack[-1][2] - stack[-1][0] <= coordis[i][2] - coordis[i][0]:
                if stack[-1][2] <= coordis[i][0]:
                    stack.append(coordis[i])
                elif stack[-1][0] < coordis[i][0]:
                    stack[-1][2] = coordis[i][0]
                    stack.append(coordis[i])
                elif stack[-1][2] <= coordis[i][2]:
                    stack.pop()
                    stack.append(coordis[i])
                else:
                    stack[-1][0] = coordis[i][2]
                    stack.append(coordis[i])
            else:
                if stack[-1][2] <= coordis[i][0]:
                    stack.append(coordis[i])
                elif stack[-1][0] <= coordis[i][0] and stack[-1][2] <= coordis[i][2]:
                    stack[-1][2] = coordis[i][0]
                    stack.append(coordis[i])
                elif stack[-1][0] < coordis[i][0] and stack[-1][2] > coordis[i][2]:
                    start, height, end = stack.pop()
                    stack.append([start, height, coordis[i][0]])
                    stack.append(coordis[i])
                    stack.append([coordis[i][2], height, end])
                else:
                    stack[-1][0] = coordis[i][2]
                    stack.append(coordis[i])
        else:
            if coordis[i][2] <= stack[-1][2]:
                continue
            elif coordis[i][0] <= stack[-1][2]:
                stack[-1][2] = coordis[i][2]
            else:
                stack.append(coordis[i])
    else:
        stack.append(coordis[i])

stack.sort()

for i in range(len(stack) - 1):
    print(stack[i][0], stack[i][1], sep = ' ', end = ' ')
    if stack[i][2] < stack[i + 1][0]:
        print(stack[i][2], 0, sep = ' ', end = ' ')

print(stack[-1][0], stack[-1][1], stack[-1][2], 0, sep = ' ', end = '')

예제와 많은 반례들을 넣어봤고 전부 출력이 잘되었지만 계속해서 출력초과가 나왔다.

해당 점들의 정보를 가져오면 된다.

먼저, 입력받은 좌표들을 시작점 오름차순 1순위, 높이 내림차순 2순위로 정렬해준다.

입력된 좌표들을 총 2번 순회하면서 왼쪽 -> 오른쪽 갈때에는 빨간점을, 오른쪽 -> 왼쪽 갈때에는 파란점을 기록해주었다.

출력을 위한 배열에는 (시작점, 높이) 를 넣어주고, 지나온 빌딩에 대한 정보는 힙에 (높이, 끝점) 으로 넣어준다. 이때 최대힙을 사용하기 위해 높이에 -를 붙여 넣어준다.

앞에서부터 좌표를 1개씩 가져오고 힙에 이미 지나온 빌딩이 있으면 다 빼준다.

힙이 비어있다면 출력배열에 (시작점, 높이)를 기록해주고 힙에 넣어준다. 건물을 만나면 항상 힙에 넣어줄것이다.

비어있지 않다면 [0]의 높이와 비교하여 현재 높이가 더 높다면 출력배열에 기록해준다.

오른쪽 -> 왼쪽 과정도 똑같이 진행하면 된다.

전체코드

import sys
import heapq

n = int(input())

coordis = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 힙이 비어있을 때 무조건 기록해주기 때문에 시작점이 같다면 높은 순으로 정렬
coordis.sort(key = lambda x: (x[0], -x[1]))
trace_heap = []
ans_heap = []

# 정방향 진행
# 시작점 최대 높이 기록
for info in coordis:
    start, height, end = info

    # 현재 시작점이 과거 건물들의 끝점을 이미 지났다면 제거
    while trace_heap and trace_heap[0][1] < start:
        heapq.heappop(trace_heap)

    # 힙에 아무것도 없다면 현재 기록
    if not trace_heap:
        heapq.heappush(ans_heap, [start, height])
    else:
        # 현재 높이가 지나온 높이보다 더 높다면 기록
        if -trace_heap[0][0] < height:
            heapq.heappush(ans_heap, [start, height])
    
    # 조건과 상관없이 지나온 자취는 항상 힙에 넣어줌
    heapq.heappush(trace_heap, [-height, end])

trace_heap.clear()
coordis.sort(key = lambda x: (-x[2]))

# 역방향 진행
# 끝점 기록
# 기본적으로 끝점은 높이가 0이다
for info in coordis:
    start, height, end = info

    # 현재 끝점이 과거 건물들의 시작점보다 작으면 이미 지나친거임
    while trace_heap and trace_heap[0][1] > end:
        heapq.heappop(trace_heap)

    # 힙에 아무것도 없다면 현재 기록
    if not trace_heap:
        heapq.heappush(ans_heap, [end, 0])
    else:
        # 현재 높이가 더 높다면 이전 높이중 가장 큰 높이 기록
        if -trace_heap[0][0] < height:
            heapq.heappush(ans_heap, [end, -trace_heap[0][0]])

    # 조건과 상관없이 항상 넣어줌
    heapq.heappush(trace_heap, [-height, start])

for skyline in sorted(ans_heap):
    print(*skyline, end = ' ')