[코딩 인터뷰 준비] 겹치는 시간 간격 찾기 알고리즘 - Interval List intersections

위의 예제를 조금 주의 깊게 살펴보면 일정한 패턴을 찾을 수 있습니다. 아직 발견하지 못했다면 최소 20~30분 정도 고민해 본 뒤 계속 진행하시길 바랍니다. 바로 답을 알면 머릿속에 남기 때문에 학습에 목적이 있다면 고민을 하고 보는 것이 도움이 될 것입니다.

문제 해결을 위한 패턴

• 교차되는 첫 번째 값은 A의 첫번째 값과 B의 첫 번째 값 중 가장 큰 값을 취한다. 교차되는 두 번째 값은 A의 두번째 값과 B의 두번째 값 중에서 가장 작은 값을 취한다.
  • 예) [0,2]와 [1,5]의 교차 간격은 [1,2]이다. 1은 0과 1 중에서 가장 큰 값이고 2는 2와 5 중에서 가장 작은 값이다.
• A와 B 배열 중 다음 원소를 선택해야 할지를 결정해야 합니다. 두 번째 값 중 작은 값의 배열을 다음 원소로 보면 됩니다.
  • 예) [0,2]와 [1,5] 중 두 번째 값이 작은 배열은 [5,10]입니다. 따라서 두 번째 교차 간격은 [5,10]과 [1,5]를 비교하면 됩니다. 위에서 말한 패턴을 적용하면 [5,5]가 다음 교차 항목이 됩니다.
• 마지막으로 염두해야 하는 것은 교차가 없는 경우입니다. 당연히 첫 번째가 두 번째 값보다 크면 해당합니다.
  • 예) 교차 간격을 계속해서 찾다 보면 [13,23]과 [8,12]를 비교하게 됩니다. 위의 패턴을 적용하면 [13,12]가 교차 간격임을 찾을 수 있습니다. 하지만 첫 번째가 두 번째 값보다 크기 때문에 교차 간격이라고 할 수 없습니다. 이런 경우에는 포함시키지 않고 다음 원소로 넘어가면 됩니다.

위의 찾은 패턴을 기반으로 알고리즘을 코드로 옮기면 원하는 답을 찾을 수 있습니다.

public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> list = new ArrayList<>();
    int i = 0, j = 0;
    while(i < A.length && j < B.length){
        int[] a = A[i];
        int[] b = B[j];
        int first = Math.max(a[0], b[0]);
        int second = Math.min(a[1], b[1]);
        if(first <= second) list.add(new int[]{first, second});
        if(a[1] < b[1]) i++;
        else j++;
    }
    return list.toArray(new int[list.size()][]);
}

코드를 보면 각 배열마다 인덱스를 따로 설정하고 조건에 따라 증가시키는 것을 알 수 있습니다. 따라서 우리가 작성한 알고리즘은 크게 보면 투 포인터 (two pointer) 알고리즘에 속한다는 것을 알 수 있습니다.

언제나 문제를 풀이 후에 혹은 풀기 전에 자신이 만든 알고리즘의 시간 복잡도(time complexity)와 공간 복잡도(space complexity)를 설명할 수 있어야 합니다. 위의 코드의 A의 길이가 n이고 B의 길이가 m이라고 할 때 A와 B의 원소를 번갈아가면서 읽는 것이 일반적이므로 시간 복잡도는 O(n + m)이며 공간 복잡도는 O(n + m)입니다.

투 포인터가 익숙하지 않다면 가장 유명한 예제로 알려진 two sum 문제를 보는 것을 추천합니다. 구글 인터뷰 준비 연습문제로 알려진 매우 유명한 문제입니다.

다음에는 까먹지 않는다면 비슷한 유형의 문제인 merge interval (간격 합치는 문제)를 해보면 좋을 것 같습니다.