lnxhigh   1년 전

스위핑으로 시도하다가 포기했던 문제인데 오늘 새로운 풀이가 떠올라서 공유해 봅니다

아이디어: 건물별로 L 에서 R 까지 루프를 돌면서 위치별로 건물의 최대 높이를 기록하고, 건물 높이가 변화하는 부분을 출력

문제점: 메모리 초과 및 시간 초과

해결 방법: 

1. 메모리 초과 - 스카이라인이 형성되는 부분은 건물의 가장자리 부분이므로 L, R 을 좌표 압축해서 최대 20만 범위의 데이터로 만들면 메모리 초과가 해결됨

2. 시간 초과 - 높이별로 건물을 정렬한 다음 가장 높은 건물부터 L 에서 R 까지 높이를 기록

여러 개의 건물 중 높이가 낮은 건물은 스카이라인을 형성하지 못한다는 점을 이용

=> 이미 지어진 건물이 있다면 그 건물은 이미 높이가 높은 건물이기 때문에 건물이 지어지지 않은 지점까지 워프한다

위치별로 건물이 있는지 없는지, 있다면 건물이 어디까지 지어져 있는지를 기록하는 배열을 사용하면 O(N) 으로 최적화됨

댓글을 작성하려면 로그인해야 합니다.