[LeetCode] 1. Two Sum (Day1)

여러가지 방법으로 해결할 수 있는 문제라서 풀어보았다.

 

1. Brute force 방식

무식한 힘으로 해석되는데, 완전탐색 알고리즘이다.

가능한 모든 경우의 수를 모두 탐색해 요구조건에 충족되는 결과만을 가져온다.

예외 없이 100%의 확률로 정답을 출력한다는 점이 좋은 점이다.

 

다른 블로그에서 빌려온 말.

• 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

   * 너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때
     따로 작성하도록 하겠다.

 

1. Brute force

반복문을 두 번 중첩으로 돌려서 시간복잡도 O(n^2)이 나왔다. 

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

 

 

 

2. Two-pass hash table

반복문을 두 개 써서 Two-pass이고, 시간복잡도 O(n)이다. 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        // Build the hash table
        for(int i=0; i<n; i++){
            numMap.put(nums[i], i);
        }

        // Find the complement
        for(int i=0; i<n; i++){
            int complement = target-nums[i];
            if(numMap.containsKey(complement) && numMap.get(complement) != i){
                return new int[]{i, numMap.get(complement)};
            }
        }
        return new int[]{}; // no solution found
    }
}

 

 

 

3. One-pass hash table

numMap.put(nums[i], i);를 if문 뒤에 해주는 이유는 만약 target이 6이고 nums가 [3, 2, 4]일 때, 저 코드가 if문 앞에 있으면 

3 + 3 = 6이 되므로 정답으로 [0, 0]이 나올 것이기 때문이다.

만약 저 코드를 if문 앞에 해주고 싶다면 i가 아닌 숫자라는 조건을 걸어줘야 할 것이다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        for(int i=0; i<n; i++){
            int complement = target - nums[i];
            if(numMap.containsKey(complement)){
                return new int[]{numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }
        return new int[]{}; // no solution found
    }
}