코딩 테스트 풀이 4 - 두 수의 합

✔ 문제

정수 수열 안에서 수열의 원소 두개의 합이 target값이 되는 경우를 찾는 문제. 매개 변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면 이 수열 안에서 두 개의 원소의 합이 정수 target이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환하고, 답이 없을 경우 [0,0] 반환, 중복 답은 없다.

제한 사항: nums의 길이 3 <= n <= 200,000

💡 접근 방법

가장 바로 머릿속에 떠오른 방법은 역시 이중 포문이다. 하지만 제한 사항을 잘 살펴보면, n <= 200,000 조건을 확인할 수 있는데, 이는 N^2 복잡도로는 시간 제한이 걸릴 수 있다는 것을 의미한다 (보통 100,000 정도가 N^2 복잡도의 최대치라고 한다). 따라서, 주어진 배열을 정렬한 후, 투 포인터를 활용해 left는 제일 작은 수를 가리키고 (arr[0]), right 는 제일 큰 수를 가리키게 초기화한다 (arr[arr.length()-1]). 그 다음, 합을 계산하고, 이 합이 타겟 값보다 작다면 left을 증가시키고, 크다면 right을 감소시킨다. 이렇게 left+right의 값을 점점 target에 가깝게 조절시키는 방법으로 접근한다. 이렇게 하면 배열을 최대 한번만 탐색하면 되므로, O(n)이 걸리고, 정렬까지 하면 O(n log n) 이 된다.

⭐ 코드

import java.util.Arrays;

public class Main
{
    static int[] Solution(int[] arr, int target)
    {
        int left = 0;
        int right = arr.length - 1;

        Arrays.sort(arr);

        while (left < right)
        {
            int sum = arr[left] + arr[right];
            if (sum > target)
            {
                --right;
            }
            else if (sum < target)
            {
                ++left;
            }
            else if (sum == target)
            {
                return new int[]{arr[left], arr[right]};
            }
        }

        return  new int[]{0,0};
    }

    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(Solution(new int[]{3,7,2,12,9,15,8},12)));
    }
}

💻 더 나은 코드 ?

위의 코드는 정렬과 순회를 합쳐 O(nlogn)의 시간복잡도를 가지게 된다. HashMap을 사용하면 O(n)에 해당 문제를 해결할 수 있다 :

static int[] Solution(int[] arr, int target)
{
    HashMap<Integer,Integer> hm = new HashMap<>();
    for (int i = 0; i < arr.length ; ++i)
    {
        hm.put(arr[i],i);
    }
       
    for (int i = 0 ; i < arr.length ; ++i)
    {
        int gap = target - arr[i];
        if (hm.containsKey(gap))
        {
            if (gap > arr[i])
                return new int[] {arr[i], gap};
            else
                return new int[] {gap, arr[i]};
        }
    }
    
    return  new int[]{0,0};
 }