Portfolio

문제

풀이

재영


/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

/*
    1. start를 기준으로 해서 일단 정렬을 시킨다.
    2. 그럼 쭉 일자로 될터인데, 결국 이것이 합쳐지려면 뒤의 start가 end보다 작아야 한다.
    3. 이 역시 스택에 넣다가, 조건이 충족되지 않으면 스택에 있는 것을 빼내서, 이를 조건에 맞게 다시 넣어준다.
*/
 const merge = intervals => {
    const stack = [];
    intervals
        .sort((a, b) => a[0] - b[0])
        .map(([ start, end ]) => {
            if (!stack.length || stack[stack.length - 1][1] < start) {
                stack.push([start, end])
            } else {
                const [ prevStart, prevEnd ] = stack.pop();
                stack.push([Math.min(prevStart, start), Math.max(prevEnd, end)])
            }
        })
    return stack;
};

저는 다음과 같은 생각을 갖고 풀었습니다.

결국 문제가 요구하는 해를 만족하려면, 맨 처음 시작 부분을 기준으로 정렬을 해야 합니다. 그렇다면 결국, 시작 부분은 이미 순서대로 정리가 되었으니, 끝쪽만 비교해주면 되기 때문입니다.

첫 번째 배열 [start1, end1] 두 번째 배열 [start2, end2] 있다면, start2가 end1보다 더 작다면, 합쳐줘야 합니다. (조건)

즉 이러한 걸 stack이란 걸 만들어서 처리해줍니다. 만약 start2가 end1보다 더 크다면 합쳐줘야 하므로 stack에서 pop해주어 처리해서 넣어줍니다. 아니라면 그냥 스택에 넣어주기만 하면 됩니다.

효성

첫 번째 풀이 `실패`


var merge = function(intervals) {
    if(intervals.length === 1) {
        return intervals;
    }
    
    intervals.sort((a,b) => a[0]-b[0]);
    
    let answer = [];

    for(let i=0; i<intervals.length-1; i++) {
        if( intervals[i][0] <= intervals[i+1][0] && intervals[i+1][0] <= intervals[i][1]) {
            const min = (intervals[i][0] - intervals[i+1][0]) < 0 ? intervals[i][0] : intervals[i+1][0];
            const max = (intervals[i][1] - intervals[i+1][1]) < 0 ? intervals[i+1][1] : intervals[i][1];
            answer.push([min, max]);
            i++;
        }
        else {
            answer.push([intervals[i][0], intervals[i][1]]);
        }
    }

    if(answer[answer.length-1][0]<= intervals[intervals.length-1][0] && intervals[intervals.length-1][0] > answer[answer.length-1][1]){
        answer.push(intervals[intervals.length-1]);
    }
    else{
        const min = (answer[answer.length-1][0] - intervals[intervals.length-1][0]) < 0 ? answer[answer.length-1][0] : intervals[intervals.length-1][0];
        const max = (answer[answer.length-1][1] - intervals[intervals.length-1][1]) < 0 ? intervals[intervals.length-1][1] : answer[answer.length-1][1];
        answer.pop();
        answer.push([min, max]);
    }

    return answer;

};

해설 참고


function merge(intervals) {
  if (!intervals.length) return intervals
  intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1])
  var prev = intervals[0]
  var res = [prev]
  for (var curr of intervals) {

    if (curr[0] <= prev[1]) {
      prev[1] = Math.max(prev[1], curr[1])
    } else {
      res.push(curr)
      prev = curr
    }
  }
  return res
}

intervals가 한 자리일 경우 예외처리를 해준다.

intervals을 정렬한다. 이 때, 앞자리를 먼저 비교한 후 같을 경우 뒷자리를 비교한다.

이전 값과 현재 값을 비교한다.

비교할 때 현재 값의 첫째 자리와 이전 값의 둘째 자리를 비교하여 이전값을 결정한다.

💡

이전 값을 계속 업데이트 하는 구조라는 것 상기하기 + 어디를 비교해야 할지 생각하기

은찬


/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    const answer = [];
    let front = 0, back = 0;
    
    intervals.sort((a, b) => {
        if(a[0] === b[0]){
            return a[1] - b[1];
        }
        else{
            return a[0] - b[0];
        }
    });
    
    front = intervals[0][0];
    back = intervals[0][1];
    
    for(let i = 1; i < intervals.length; i++){
        if(back < intervals[i][0]){
            answer.push([front, back]);
            front = intervals[i][0];
            back = intervals[i][1];
        }
        else if(back < intervals[i][1]){
            back = intervals[i][1];
        }
    }
    
    answer.push([front, back]);
    
    return answer;
};

우선 주어진 intervals를 오름차순으로 정렬을 했습니다.

정렬은 각 배열의 0번째 요소가 더 작은 값이 앞으로 오게 되며, 만약 0번째 값이 같게 된다면 1번째 값이 더 작은 배열을 앞에 오게 정렬합니다.

그래야 오버랩 할 수 있는지를 비교할 수 있기 때문입니다.

front와 back 변수를 이용해, intervals의 각 배열을 순회합니다.

front는 오버랩의 시작 숫자, back은 오버랩이 끝난 숫자를 뜻합니다.

처음 시작은 정렬된 intervals의 0번째 요소입니다.

front = intervals[0][0], back = intervals[0][1] 로 지정합니다.

시작은 0번째 요소였으니, for문은 1번째 요소부터 시작하면 됩니다.

만약 back이 현재 intervals[i][0]보다 작다면 새로운 인터벌이 시작된다는 뜻이기 때문에, 지금까지의 인터벌을 answer에 넣어주도록 합니다.

이후 front와 back을 새로운 인터벌로 지정해야 하기 때문에 각각 intervals[i][0]과 intervals[i][1]로 갱신해줍니다.

그렇지 않고 back이 현재 intervals[i][1]이라면 오버랩 할 수 있기 때문에 back을 intervals[i][1]로 갱신해 준 다음 반복문을 계속 진행해 줍니다.

for문이 끝나면 한번 더 front와 back을 answer에 넣어 마지막 인터벌까지 저장하면 끝입니다!

Merge Intervals

문제

풀이

첫 번째 풀이 실패

해설 참고

첫 번째 풀이 `실패`