자바 코딩테스트 강좌, 어떤 알고리즘으로 풀어야 할까

1. 문제 설명

다음은 주어진 배열에서 두 수의 합이 특정 값이 되는 인덱스를 찾는 문제입니다.

문제: 배열 nums와 정수 target가 주어질 때, nums에서 두 수의 합이 target이 되는 인덱스 두 개를 반환하시오. 각 입력은 오직 하나의 해답이 존재하며, 동일한 요소를 두 번 사용할 수는 없습니다. 반환할 인덱스는 0부터 시작하며, 반환 값은 배열 형태로 하십시오.

예시:

• 입력: nums = [2, 7, 11, 15], target = 9
• 출력: [0, 1] (2 + 7 = 9)

2. 문제 분석

이 문제는 여러 번 출제된 매우 흔한 문제입니다. 주어진 배열에서 두 수를 찾아야 하므로, 가장 먼저 떠오르는 방법은 이중 반복문을 사용하는 것입니다. 하지만, 이 방법은 O(n²)의 시간 복잡도를 가지므로 비효율적입니다.

최적의 방법을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다. 이 방법에서는 해시맵을 활용하여 탐색하는 방식으로 접근하겠습니다.

3. 알고리즘 설계

우리는 다음과 같은 단계로 알고리즘을 설계할 것입니다:

1. 빈 해시맵을 생성합니다.
2. 모든 숫자를 반복하여 처리합니다.
3. 각 숫자에 대해 target - 현재 숫자이 해시맵에 존재하는지 확인합니다.
4. 존재한다면 두 인덱스를 반환하고, 없다면 현재 숫자를 해시맵에 추가합니다.

이 알고리즘의 핵심은 한 번의 반복으로 두 수를 찾을 수 있도록 하는 것입니다.

4. 자바 코드 구현

이제 자바를 사용하여 이 문제를 해결하는 코드를 작성해 보겠습니다.

import java.util.HashMap;

public class TwoSum {
    public static int[] findTwoSum(int[] nums, int target) {
        HashMap numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            numMap.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = findTwoSum(nums, target);

        System.out.println("인덱스: [" + result[0] + ", " + result[1] + "]");
    }
}

위 코드는 매우 간단하면서도 효율적인 방식으로 문제를 해결합니다. HashMap을 사용하여 각 숫자의 인덱스를 저장하고, target과의 차이를 계산하여 탐색합니다.

5. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. n은 입력 배열의 길이입니다. 해시맵에 숫자를 추가하는 연산과 검색하는 연산 모두 평균적으로 O(1)의 시간 복잡도를 가지므로, 전체 반복 과정에서 O(n)으로 제공할 수 있습니다. 공간 복잡도도 O(n)으로 해시맵에 입력 숫자만큼 저장되기 때문입니다.

6. 추가 고려 사항

이 문제를 해결할 때 몇 가지 추가적인 사항을 고려해야 합니다:

• 중복 숫자가 있을 경우: 동일한 숫자가 두 번 사용되면 안 됩니다.
• 해시맵의 성능: 자바의 해시맵은 평균적으로 O(1)의 시간 복잡도를 가집니다. 하지만 입력이 특정 패턴이라면 O(n)의 최악의 경우에 도달할 수 있습니다.
• 예외 처리: 해답이 없을 경우를 대비해 적절한 예외를 던져주어야 합니다.

7. 마무리

오늘은 특정한 프로그래밍 문제를 해결하는 방법으로 해시맵을 활용하는 알고리즘을 알아보았습니다. 실무에 가까운 상황에서의 응용 능력이 중요하므로, 다양한 문제를 풀어보면서 연습하는 것이 좋습니다. 취업을 위한 알고리즘 문제해결 능력을 발전시키기 위해 꾸준히 노력하시기 바랍니다.