[Interval][Medium] 57. Insert Interval

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

 

Q. 주어진 구간 정보배열 intervals가 있고, 추가 될 구간 newInterval 이 있다. 이때 newInterval을 추가한 상태로 새로운 구간 정보를 구성하라. 

 

Solution. 

 그냥 있는 그대로의 상태에서 바로 이런 저런 시도를 하려다 보니, 풀이 시간이 길어졌다. 

 최대로 복잡한 구간을 최대한 간결한 코드로 풀어내는 것이 코딩문제 풀이의 핵심이다. 

 이것도 최대한 그렇게 해 본다. 

 

 주어진 구간 interval은 이미 정렬된 구간 데이터 이다. 

 따라서 새 구간 정보를 주어진 데이터에 넣으면 되는데, 이때 아래의 규칙에 따른다. 

 

 우선 새 구간 정보와 기존 index 순서대로 구간 정보 중, 출력 구간 정보에 넣을 구간을 선택한다. 

 어떻게? 시작이 작은 녀석을 먼저 선택한다. 

 

 이 선택된 nextInterval과 현재 새로운 구간의 마지막 구간을 비교한다. 

 즉, 이 두 구간을 필요에 따라 merge 한다. 

 

 기존 구간의 마지막 값이 next 구간의 시작값보다 작다면, 겹치는 데가 없다. 그냥 새 구간을 넣으면 된다. 

 그렇지 않다면 겹친다는 것이다. Merge를 하되, 추가할 필요 없이, 마지막 구간 값의 종료 값을 두 값 중 더 큰 값으로 갱신한다. 

 

  이 과정을 끝까지 반복한다. 

 

  즉, 

   1. 다음 구간 정보의 선택

   2. 병합 여부 결정

   3. 필요에 따라 병합

 

   이렇게 코드를 만들어 본다. 

 

 

public int[][] Insert(int[][] intv, int[] newIntv) 
{
    List<int[]> ret = new List<int[]>();

    int idx = 0;
    bool addedNew = false;
    while(!addedNew || idx<intv.Length)
    {
        int[] next = null;
        if(idx >= intv.Length)
        {
            if(!addedNew)
            {
                next = newIntv;
                addedNew = true;
            }
        }
        else 
        {
            if(addedNew)
                next = intv[idx++];
            else 
            {
                if(intv[idx][0] < newIntv[0])
                    next = intv[idx++];
                else 
                {
                    next = newIntv;
                    addedNew = true;
                }
            }
        }
        if(next == null)    break;

        if(ret.Count == 0)
            ret.Add(next);
        else 
        {
            int[] prev = ret[ ret.Count-1 ];
            if(prev[1] < next[0])   // 1, 3 --- 6, 7       => (1,3) (6,7)
                ret.Add(new int[]{ next[0], next[1] } );
            else                    // 1, 4(6), --- 2, 5   => (1,5) or (1,6)
                prev[1] = Math.Max(prev[1], next[1]);
        }
    }

    return ret.ToArray();
}

 

 

적절한 결과를 얻었다.