[리트코드] 56. Merge Intervals

문제

https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

 

문제 설명 및 풀이과정

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

 

이러한 예제가 있지만 여기서는 아래와 같이 3개의 원소가 있을 경우로 설명하겠습니다.

[[1,3],[2,6],[8,10]]

1	2	3	4	5	6	7	8	9	10
[1,3]	[1,3]	[1,3]
	[2,6]	[2,6]	[2,6]	[2,6]	[2,6]
							[8,10]	[8,10]	[8,10]

겹치는 구간을 찾고 겹치는 구간이 있으면 합쳐주면 됩니다.

이 예제에서는 [1,3]과 [2,6]이 겹침으로 [1, 6]이 됩니다.

이 예제에서 나와야 되는 output은 [[1,6], [8,10]]이 됩니다.

 

 

그럼 겹치는 부분을 확인하는 방법은 무엇일까요?

비교할 2개의 원소 배열에 첫 번째 원소 배열[1], 두 번째 배열[0]을 비교하면 됩니다.

첫 번째 원소 배열[1] >= 두 번째 배열[0] 이면 겹치는 부분이 발생하게 됩니다.

[1,3] [2,6]

이 예제를 보시면 3, 2를 비교하면 되고

3 >= 2 임으로 겹치는 구간 발생 및 합치기

 

합치는 방법

그럼 두 원소가 겹치는 부분이 있는 걸 확인했으니 합쳐져야 됩니다.

저는 Math.min, Math.max를 사용해서 해결했습니다.

[1,3] [2,6]

이 두 개의 원소 배열이 겹치는 구간이 있다는 걸 확인했으면 한 배열에 담아줍니다.

[1, 3, 2, 6] 

여기서 가장 작은 수, 큰 수를 찾아주면 됩니다.

그러면 [1, 6]이 됩니다.

 

이 방법을 아래와 같이 코드로 구성했습니다.

---

소스코드

var merge = function(intervals) {
    if(intervals.length === 1) return intervals;
    
    intervals = intervals.sort((a,b)=> a[0] - b[0]);    
    
    let result=[];
    let now = intervals[0];
    for(let i=1; i<intervals.length; i++){        
        let [prveEnd, nextStart] = [now[1], intervals[i][0]];
        
        if(prveEnd >= nextStart){
            let nums = [...now, ...intervals[i]];
            now = [Math.min(...nums), Math.max(...nums)]
        }else{
            result.push(now);
            now = intervals[i];
        }
        
        if(i === intervals.length-1) result.push(now);
    }
    return result
};

 

위에서 문제 설명에서 얘기했던 부분을 코드로 작성한 구간은

let result=[];
let now = intervals[0];
for(let i=1; i<intervals.length; i++){        
    let [prveEnd, nextStart] = [now[1], intervals[i][0]];

    if(prveEnd >= nextStart){
        let nums = [...now, ...intervals[i]];
        now = [Math.min(...nums), Math.max(...nums)]
    }else{
        result.push(now);
        now = intervals[i];
    }

    if(i === intervals.length-1) result.push(now);
}
return result

이 부분입니다.

 

 

그러나 추가적으로 코드 두줄을 더 작성했습니다.

추가한 코드

if(intervals.length === 1) return intervals;

이 코드는 아래와 같이 intervals안에 원소가 하나만 있을 경우 처리한 코드입니다.

[[1,3]]

 

intervals = intervals.sort((a,b)=> a[0] - b[0]);

이 코드는 아래와 같이 순서가 이상할 경우를 위해 정렬해준 코드입니다.

[[1,4],[0,0]]

---