1933번 - 스카이라인
스위핑으로 시도하다가 포기했던 문제인데 오늘 새로운 풀이가 떠올라서 공유해 봅니다
아이디어: 건물별로 L 에서 R 까지 루프를 돌면서 위치별로 건물의 최대 높이를 기록하고, 건물 높이가 변화하는 부분을 출력
문제점: 메모리 초과 및 시간 초과
해결 방법:
1. 메모리 초과 - 스카이라인이 형성되는 부분은 건물의 가장자리 부분이므로 L, R 을 좌표 압축해서 최대 20만 범위의 데이터로 만들면 메모리 초과가 해결됨
2. 시간 초과 - 높이별로 건물을 정렬한 다음 가장 높은 건물부터 L 에서 R 까지 높이를 기록
여러 개의 건물 중 높이가 낮은 건물은 스카이라인을 형성하지 못한다는 점을 이용
=> 이미 지어진 건물이 있다면 그 건물은 이미 높이가 높은 건물이기 때문에 건물이 지어지지 않은 지점까지 워프한다
위치별로 건물이 있는지 없는지, 있다면 건물이 어디까지 지어져 있는지를 기록하는 배열을 사용하면 O(N) 으로 최적화됨
댓글을 작성하려면 로그인해야 합니다.
lnxhigh 1년 전
스위핑으로 시도하다가 포기했던 문제인데 오늘 새로운 풀이가 떠올라서 공유해 봅니다
아이디어: 건물별로 L 에서 R 까지 루프를 돌면서 위치별로 건물의 최대 높이를 기록하고, 건물 높이가 변화하는 부분을 출력
문제점: 메모리 초과 및 시간 초과
해결 방법:
1. 메모리 초과 - 스카이라인이 형성되는 부분은 건물의 가장자리 부분이므로 L, R 을 좌표 압축해서 최대 20만 범위의 데이터로 만들면 메모리 초과가 해결됨
2. 시간 초과 - 높이별로 건물을 정렬한 다음 가장 높은 건물부터 L 에서 R 까지 높이를 기록
여러 개의 건물 중 높이가 낮은 건물은 스카이라인을 형성하지 못한다는 점을 이용
=> 이미 지어진 건물이 있다면 그 건물은 이미 높이가 높은 건물이기 때문에 건물이 지어지지 않은 지점까지 워프한다
위치별로 건물이 있는지 없는지, 있다면 건물이 어디까지 지어져 있는지를 기록하는 배열을 사용하면 O(N) 으로 최적화됨