🏷️1. Two Sum

---

1. 문제 설명

• 주어진 정수 배열 nums와 정수 target이 주어졌을 때, 두 숫자를 더해서 target이 되는 인덱스를 반환하십시오.

• 각 입력이 정확히 하나의 해결책을 가지고 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.

• 어떤 순서로든 답을 반환할 수 있습니다.

---

2. 접근 방법

이중 반복문을 사용하여 모든 가능한 경우를 확인하는 브루트 포스 방법을 사용하여 해결하였습니다.

1. 배열 nums에서 처음부터(i= 0) 끝까지(nums.length) 조회하는 반복문을 만들고, 첫 번째 반복문의 index부터(i) 끝까지(nums.length) 조회하는 반복문을 하나 더 만들어 모든 경우의 수를 비교하도록 코드를 작성하였습니다.
2. 모든 경우의 수를 확인하며 target과 같은 연산값을 찾으면 결과값을 반환하는 배열에 해당 index i, j를 저장하여 반환합니다.

---

3. 구현 코드

//Brute Force
import java.util.Hashtable;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int len = nums.length; // nums의 길이
        int[] re = new int[2]; // 결과값으로 반환할 배열
        
        Loop1 :
        for(int i = 0; i < len; i++){
            for (int j = i + 1; j < len; j++) {
                if(nums[i] + nums[j] == target){
                    re[0] = i;
                    re[1] = j;
                    break Loop1;
                }
            }
        }

        return re;
    }
}

• 시간 복잡도 : O(N^2)
• 공간 복잡도 : O(1)

---

4. 개선 사항

• 브루트 포스로 모든 경우의 수를 확인하여 결과값을 찾을 수 있었지만 시간 복잡도가 O(N^2)이였습니다.
• 위의 코드에서 HashMap 을 사용하여 메모리를 조금 더 사용하지만 시간복잡도를 O(N)으로 줄일 수 있는 코드로 개선해 보았습니다.
• HashMap에 Key : Vaule 를 nums[i] : i값으로 저장하면서 target - nums[i] 연산값이 존재하는지 조건 처리를 합니다.
• 연산값이 존재한다면 원하는 결과값을 찾았으므로 해당 index들을 저장하고 반환합니다.

// Hash Table
class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int len = nums.length; // nums의 길이
        int[] re = new int[2]; // 결과값으로 반환할 배열
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        Loop1 :
        for(int i = 0; i < len; i++){
            int n = target - nums[i];
            if(map.containsKey(n)){
                re[0] = i;
                re[1] = map.get(n);
                break Loop1;
            }
            map.put(nums[i], i);
        
        }

        return re;
    }
}

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

---

5. 최종 회고

• 항상 처음은 완전 탐색으로 문제를 고민하고 있는 것 같습니다. 그래서 문제가 원하는 자료구조, 알고리즘을 제대로 파악하여 접근하기 보다는 생각한대로 시도를 해보고 있습니다.
• 그래서 많은 시행착오를 겪으며 배우는 부분도 많지만 시간 투자가 생각보다 많이 소비하고 있습니다.
• 한번 배운 자료구조와 알고리즘에 대해 더 깊이 파고들어 다음에 잘 활용할 수 있도록 하는 것이 앞으로 저에게 도움이 될 것 같습니다.😊

---

6. 참고

• [JAVA] HashTable의 개념 및 사용법 정리