프로그래밍 면접 문제 1 : Array Pair Sum

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

대학 졸업생들의 입사지원 시즌이 돌아왔고, 기술 회사들은 정직원 및 인터쉽 자리를 위한 면접을 시작했습니다. 저는 지난해 이맘때쯤 인턴쉽을 위해서 면접을 여러차례 봤습니다. 마침내, 마이크로 소프트의 Bing에서 인턴쉽 기회를 얻었고, 다음해 여름 정직원으로 입사했습니다. 올해는 면접 볼 예정은 없지만, 제 친구 여러명이 면접을 위해서 준비하고 있길래, 괜찮은 수준의 면접 문제와 제 나름의 풀이법을 공유하는 것이 좋겠다고 생각했습니다. 저는 최근에 특히 이 질문을 자주 받습니다: 주어진 정수형 배열에서 두 수를 더한 결과가 k가 되는 서로 다른 숫자 쌍을 모두 구하라.

N의 크기를 갖는 배열이 있다고 가정합니다. 이 문제를 푸는 다소 순진한(?) 방법은 배열을 순회해서 두 수를 더한 결과가 K가 되는 요소가 있는지 찾는 방법이며, 이 방법의 복잡도는 O(N^2) 입니다. 이 방법은 최적화와는 거리가 멀기 때문에 여러분은 면접에서 이 방법을 대답하길 원치 않을 겁니다. 좀 더 효율적인 해결책은 배열을 정렬하고, 배열의 처음과 끝에서부터 숫자를 검색하는 두 변수를 이용하는 방법입니다. left와 right번째 항목을 서로 더한 결과가 k와 동일하면 이 순서쌍을 출력합니다. 두 수를 더한 결과가 k보다 작으면 left 변수를 증가시키고, 두 수를 더한 결과가 k보다 크면 right 변수를 하나 감소시켜서 left와 right 변수가 서로 만날 때까지 반복합니다. 배열을 정렬하기 때문에 이 방법의 복잡도는 O(NlogN) 입니다. 아래는 이 해결책의 C# 예제 코드입니다:

void PairSum1(int[] arr, int k)
{
    if (arr.Length < 2)
        return;

    Array.Sort(arr);

    int left = 0;
    int right = arr.Length - 1;

    while (left < right)
    {
        int currentSum = arr[left] + arr[right];

        if (currentSum == k)
        {
            Console.WriteLine("{0} : {1}", arr[left], arr[right]);
            ++left;
        }
        else if (currentSum < k)
            ++left;
        else
            --right;
    }
}

배열 기반의 면접 문제 대부분이 배열 정렬을 통해서 O(NlogN)의 복잡도로 해결됩니다. 하지만, 면접자 중에는 선형적인 시간 복잡도를 갖는 해결책을 원하는 경우도 있습니다. 그래서 좀 더 최적화된 O(N) 복잡도의 해결책을 찾아보겠습니다. 그 전에 면접자에게 명확히 해두어야 할 것이 있는데, 동일한 숫자 쌍이 하나 이상 있는 경우에 두번 출력할지 여부를 확인해야 합니다. 예를 들어, 배열 [1, 1, 2, 3, 4]가 있고 찾으려는 더한 결과 값이 4라고 가정하겠습니다. 이 경우 (1, 3) 숫자 쌍을 두번 출력할지 여부를 확인해야 합니다. 또한 반대의 숫자 쌍인 (3, 1)도 두번 출력할지 확인합니다. 여기에서는 결과를 간단히하기 위해서 각 숫자 쌍을 한 번씩만 출력하겠습니다. 따라서 결과는 (1, 3) 이 됩니다. (2, 2)는 서로 다른 값이 아니기 때문에 조건에 만족하지 않아서 출력하지 않습니다.

배열을 처음부터 순회하면서 seen 자료 구조 안에 k 요소가 있는지 확인합니다. k 요소가 있으면 숫자 쌍을 찾았기 때문에 output에 추가합니다. k 요소가 없으면, 아직 숫자 쌍에 속하지 않기 때문에, seen 자료 구조에 넣습니다. 배열을 한번만 순회하기 때문에 복잡도는 O(N)이며, 배열을 순회하면서 각 배열의 요소가 seen 안의 숫자와 숫자 쌍을 이루는지 아니면 seen 자료구조에 넣을지 확인합니다. List 자료구조에 삽입 및 검색 연산은 모두 평균 O(1)이기 때문에, 알고리즘의 복잡도는 전체 O(N)입니다. 전체 코드는 다음과 같습니다.

void PairSum2(int[] arr, int k)
{
    if (arr.Length < 2)
        return;

    HashSet<int> seen = new HashSet<int> ();
    HashSet<int[]> output = new HashSet<int[]> ();

    for (int ix = 0; ix < arr.Length; ++ix)
    {
        int target = k - arr [ix];
        if (!seen.Contains (target))
            seen.Add (arr [ix]);
        else
            output.Add (new int[] { Math.Min (arr [ix], target), Math.Max (arr [ix], target) });
    }

    foreach (int[] outputPair in output)
    {
        Console.WriteLine("{0} : {1}", outputPair[0], outputPair[1]);
    }
}

다음글 – 프로그래밍 면접 질문 2 : Matrix Region Sum