[leetcode] Insert Interval

문제 설명

• 문제 링크
• [시작, 끝] 구간이 담겨있는 intervals 배열이 주어진다. 구간은 서로 겹쳐있지 않고, 시작 값을 기준으로 오름차순 정렬되어 있다. 여기에 새로운 구간인 newInterval을 추가해야 한다. newInterval을 추가했을 때 겹쳐지는 부분이 생기면 병합(merge) 해야 한다.
• 제약 조건
  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start <= end <= 10^5
  • newInterval.length == 2

풀이

풀기 전

• 두 가지 방법이 떠올랐다.
  • (1) intervals를 순회하면서 newInterval 구간이 포함됐는지 체크하고, 포함된 형태에 따라 merge 하는 방법이다. intervals를 한 번 순회하기 때문에 시간 복잡도가 O(intervals.length) 이다. 그래서 빠르지만, newInterval이 구간에 포함됐는지 체크하는게 번거로울 거 같았다.
  • (2) 좌표를 나타내는 배열을 하나 만든 뒤 intervals를 순회하면서, start를 만났을 땐 1을 더하고 end를 만났을 땐 -1을 뺀다. 그 후 좌표 배열을 순회하면서 누적합이 0이 되는 순간을 기준으로 구간을 나누는 방법이다. 시간 복잡도는 좌표 배열의 크기에 따른 O(end 최대값)이다. (1) 방법보다는 느리지만 심플해보였다.
• 처음에는 심플해보이는 (2) 방식으로 진행하려고 했다. 그런데 start와 end가 같을 수 있다는 제약 조건을 고려하지 않았다. 그래서 코드가 복잡해졌다. (1) 방식보다 오래 걸리면서 코드가 복잡해지면 굳이 (2) 방식을 고를 이유가 없다고 생각되어, 중간에 (1) 방식으로 바꿨다.

코드

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    	// intervals가 비어있으면 newInterval을 그대로 사용
        if (intervals.size() == 0)
            return vector<vector<int>>{newInterval};

        vector<vector<int>> ret;
        bool merged = false;

        int newStart = newInterval[0];
        int newEnd = newInterval[1];

        int start, end;
        int tmpStart = newStart;
        for (int i=0; i<intervals.size(); i++) {
            auto& interval = intervals[i];
            start = interval[0];
            end = interval[1];

			// merged == true이면 newInterval이 이미 적용됐으므로 현재 구간 그대로 추가
            // 또는, 현재 구간이 newInterval 전에 끝나면 그대로 추가
            if (merged || end < newStart) {
                ret.push_back(interval);
                continue;
            }

            // 조건에 따라 merge
            tmpStart = min(start, tmpStart);
            if (newEnd < start) {  // (1) newEnd가 이전 구간까지만 포함하는 경우
                ret.push_back({tmpStart, newEnd});
                ret.push_back(interval);
                merged = true;
            } else if (newEnd < end) {  // (2) newEnd가 현재 구간에 포함되는 경우
                ret.push_back({tmpStart, end});
                merged = true;
            }
        }
        // 마지막까지 merge가 안 됐다는 건 newEnd가 가장 뒤에 있다는 의미
        // (1) newInterval이 아무 구간도 포함 못하고 좌표 맨 뒤에서 홀로 있는 경우
        // (2) newInterval이 겹치는 구간을 포함하고 있으나, newEnd가 맨 뒤에 있어서 체크되지 못하고 for문이 끝나는 경우.
        if (!merged)
            ret.push_back({tmpStart, newEnd});

        return ret;
    }
};

• intervals에 있는 구간을 순회한다.
  • 추가해야 하는 구간(newInterval)이 이미 merge 되어 있거나, 현재 구간이 newInterval에 겹치지 않고 앞에 있다면 현재 구간을 반환할 벡터에 그대로 추가한다.
  • 아직 newInterval이 merge 되지 않았고, 현재 구간에 겹칠 가능성이 있다면 merge 조건을 체크한다.
    • (1) newInterval의 end가 현재 구간엔 겹치지 않지만, 이전 구간을 포함하고 있는 경우이다. intervals: [[1, 3], [5, 7]], newInterval: [2, 4]인 경우, [5, 7] 구간을 체크하고 있을 때에 해당한다. 조건을 만족하면 우선 병합된 구간을 추가하고, 현재 구간을 그 뒤에 추가한다.
    • (2) newInterval의 end가 현재 구간에 겹치는 경우이다. intervals: [[1, 3], [5, 7]], newInterval: [4,6]인 경우, [5, 7] 구간을 체크하고 있을 때에 해당한다. 조건을 만족하면 병합된 구간을 추가한다.
• 순회가 끝났는데 merge == false라면 아직 newInterval 적용이 되지 않았다는 의미이다. newInterval의 end가 가장 뒤에 있는 경우에 해당한다. 저장해뒀던 start와 함께 추가해준다.

푼 후

• 처음에는 조건문이 많고 코드도 더 복잡했다. 그림으로 그리면서 여러 경우의 수를 고려하며 작성해서 그랬다. 테스트 통과 못하는 부분 꾸역꾸역 채워가며 통과하긴 했는데 마음에 드는 코드는 아니었다. 다른 사람들 코드를 보니 생각보다 간결하게 짤 수 있었다. 너무 어렵게 생각해서 더 꼬인 거 같다.
• 요 문제는 제약 조건을 잘 고려해야 하는 문제인 거 같다.