알고리즘 - Two Sum

1. Brute Force

알고리즘

브루트 포스 접근법은 간단하다. 루프 안에서 각 원소값인 𝓍 와 target -  𝓍 와 일치하는 다른 값을 찾으면 된다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }

        return null;
    }
}

 

시간 복잡도 분석

- 시간 복잡도 : O(n2)

값을 찾기 위해 돌리는 루프와 그 안에서 남은 원소의 값을 돌리는 루프가 있기에 시간복잡도는 O(n2)가 된다.

- 공간 복잡도 : O(1)

추가적인 공간 없이 입력된 값을 통해서 값을 도출해 낼 수 있어서 공간 복잡도는 O(1)이 된다.

2. Two-pass Hash Table

알고리즘

런타임 복잡도를 개선시키기 위해, 우리는 배열 안에서 더 효율적인 방법을 찾을 필요가 있다.
보완할 수 있는 부분을 찾아보기 위해 인덱스를 사용해 보자. 각 값들의 매핑을 유지하는 최고의 방법은 해쉬 테이블(Hash Table)이다.

 

우리는 공간복잡도가 약간 복잡해지는 대신 시간 복잡도를 O(n)에서 O(1)로 줄일 수 있다.

해쉬테이블은 빠르게 탐색할 수 있는 자료구조이기에, 해당 문제에서 사용하기 알맞다. 하지만 해쉬 테이블 안에서 충돌이 발생할 경우 시간복잡도가 O(n)이 될 가능성이 있다. 그러나 해쉬 테이블을 잘만 사용한다면 크게 문제는 없을 것이라 판단한다.

 

해당 알고리즘을 사용하는 간단한 방법은 2개의 이터레이션(iteration)을 사용하는 것이다.

첫 번째 이터레이션에서 주어진 배열에 값을 키로, 배열의 인덱스는 해쉬 테이블의 값으로 추가하자.

두 번째 이터레이션에서는 주어진 배열을 돌면서 target -  𝓍 로 된 값과 일치하는 값을 키로 해쉬 테이블에서 찾아보자.

(자기 자신을 찾아서는 안 되기에 조건에 추가해 주자.)

class Solution {
	public int[] twoSum(int[] nums, int target) {
    	Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
        	map.put(nums[i], i);
        }
        
        for (int i = 0; i < nums.length; i++) {
        	int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
            	return new int[] { i, map.get(complement) };
            }
        }
        
        return null;
    )
}

 

시간 복잡도 분석

- 시간 복잡도 : O(n)

반복문을 2개를 사용하였지만 해쉬테이블을 사용하였기에, 탐색 시간이 기존 O(n)에서 O(1)이 되었다.

그렇기에 전반적인 시간 복잡도는 O(n)이 된다.

- 공간 복잡도 : O(n)

해쉬테이블을 사용하였기에 추가적인 공간을 주어진 배열의 길이만큼 필요로 하게 되어 공간 복잡도는 O(n)이 된다.

2. One-pass Hash Table

알고리즘

잘 생각해 보면 우리는 Two-pass Hash Table을 한 번에 처리할 수 있다. target -  𝓍  에 대한 값을 검사하면서 만약 그 값이 없다면,

해쉬 테이블에 넣음으로, 배열이 끝까지 갈 시에는 해쉬테이블에도 배열이 지나온 값만큼 담기게 된다.

class Solution {
	public int[] twoSum(int[] nums, int target) {
    	Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0l i < nums.length; i++) {
        	int complement = target - nums[i];
            if (map.containsKey(complement)) {
            	return new int[] { map.get(complement), i);
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

 

시간 복잡도 분석

- 시간 복잡도 : O(n)

반복문을 1개를 사용하였고 탐색 시간은 Two-pass와 동일하게 O(1)이기에 시간 복잡도는 O(n)이 된다.

- 공간 복잡도 : O(n)

최악의 경우에는 추가적인 공간을 주어진 배열의 길이보다 약간 작게 필요로 하기에 공간 복잡도는 거의 O(n)이다.