[LeetCode] 57. Insert Interval (Java)

문제

 

https://leetcode.com/problems/insert-interval/

Insert Interval - LeetCode

 

풀이

 

난이도: Medium 

 

start와 end로 구성된 구간이 주어질 때, 새로운 구간의 삽입으로 변경된 구간을 반환하는 문제.

사실 주어지는 모든 구간은 겹치는(overlapping) 구간이 없이 모두 정렬되어 있지만, 주어지는 모든 구간도 겹치는 부분을 판단해 주는 문제로 풀어버렸다.

이런 풀이도 결과에는 영향이 없으므로 정답은 통과했다.

 

일단, 구간들은 오름차순으로 정렬되어 있으므로 newInterval이 들어가는 부분을 찾아야 한다.

newInterval을 구간에 추가해서 다시 정렬하는 것이 가장 간단하겠지만, 단 하나의 원소만을 위해 정렬을 사용하는 것은 비효율적이고 이미 정렬된 배열에서는 위치를 쉽게 찾을 수 있다.

 

위치를 찾았다면 insertedIntervals라는 새로운 배열에 값들을 복사해서 newInterval이 추가된 배열을 만든다.

이제 순서대로 순회하면서 다음 start 지점이 이번의 end보다 작거나 같다면 두 구간은 합쳐질 수 있으므로

새로운 구간의 end는 두 구간 중에 더 큰 값이 된다.

 

물론, newInterval이 영향을 미치는 구간만 합쳐주는 것이 더 효율적이다.

 

코드