[LeetCode Medium] Merge Intervals JavaScript

IT공부중·2020년 5월 5일
0

알고리즘

목록 보기
26/49

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

문제 설명

[[1,3],[2,6],[8,10],[15,18]] 과 같은 input이 주어지면 [[1,6],[8,10],[15,18]]
로 줄이면 된다. [1,3] 과 [2,6]이 구간이 이어지기 때문에 합치면 된다!!

[[1,4],[4,5]] 주어진 경우에도 [[1,5]] 이런식으로 합칠 수 있다.

빈 배열이 주어졌을 경우에는 빈 배열을 반환해야한다.

문제 풀이

일단 정렬이 된 상태로 주어지는 것이 아니다. 그렇기 때문에 정렬을 해주어야 제대로 된 풀이를 할 수 있다. 그래야 구간을 제대로 확인할 수 있기 때문이다. 나는 mergeArray라는 함수를 만들어서 합칠 수 있는지 없는지 판단하여 답에 넣기로 하였다.

첫번째 배열의 두번째 원소와 두번째 배열의 첫번째 원소를 비교해서 두개가 겹치면 현재 answer를 하나 빼고 조건에 맞춰 push 해주었다.

겹치지 않는다면 그냥 두번째 배열을 push 해주면 된다.

내 코드

function mergeArray(answer, first, second) {
    if(first[1] >= second[0]) {
        answer.pop();
        answer.push([Math.min(first[0], second[0]), Math.max(first[1], second[1])]);
    }
    else {
        answer.push(second);
    }
}
var merge = function(intervals) {
    const answer = [];
    if(intervals.length === 0) {
        return answer;
    }
    intervals.sort((a,b) => a[0]-b[0]);
    answer.push(intervals[0]);

    for(let i = 1; i < intervals.length; i++) {
        mergeArray(answer, answer[answer.length-1], intervals[i]);
    }
    return answer
};

배운점

쟤 코드에서는 쓰지 않았지만 sort를 할 때 2개의 기준으로 정렬을 할 수 있는 방법을 알게 되었습니다.
sort 안에는 compareFunction이라는 콜백함수를 넣어줄 수 있습니다.

function compareFunction(a,b) {
	return a-b; // 오름차순으로 정렬합니다. 
}
function compareFunction2(a,b) {
	return b-a; // 내림차순으로 정렬합니다. 
}

위의 식에서는

(a,b) => a[0]-b[0]

이라는 식을 넣어줬는데 위 식은 a와 b의 0번 index를 기준으로 오름차순으로 정렬하라는 의미이다.

여기까지는 원래 알고 있었는데 이제 a[0], b[0]이 같을 때 a[1]과 b[1]을 기준으로 어떻게 정렬해야하는지 몰랐었는데

(a,b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]

다른 사람의 코드에서 이런식으로 사용하는 것을 보았다. 0번째 인덱스가 서로 같으면 1번째 인덱스로 비교하고 다르면 0번째 인덱스로 비교하라는 코드이다. 그래서 앞으로도 유용하게 써먹을 수 있을 것 같다.

profile
3년차 프론트엔드 개발자 문건우입니다.

0개의 댓글