[Day1] Two Sum

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

<문제 설명>

int형인 nums 배열과 변수 target이 있다.

배열에서 2개의 숫자 합이 target 값이 되도록 하는 인덱스를 리턴하도록 만든다.

 

 

<풀이 과정>

1. Brute-force 사용하기

'무식한 힘'이라는 알고리즘으로 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 문제를 보자마자 첫 번째로 생각난 방법

 

2. HashMap 사용하기

Leetcode에서 O(n^2) 복잡도보다 적은 다른 알고리즘을 찾을 수 있냐고 하며 HashMap을 사용해보라고 해서 생각해보았다. 하지만 아직 HashMap을 잘 쓸 줄 모르기 때문에 공부하고 완성 코드를 보면서 이해하였다.

첫 번째로 Hashing이란 비교연산이 아닌, 산술적인 연산을 이용하여 key가 있는 위치를 계산하여 찾아가는 계산 탐색 방법이다. HashMap은 Hashing을 사용하는 Map형 자료구조인데, 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다. JAVA에서 HashMap은 util 패키지의 클래스로 정의되어있기에 바로 사용가능하다. HashMap의 다양한 API들을 맨 아래 링크를 통해 볼 수 있다. 추가로 getOrDefault() 메소드는 찾는 키가 존재한다면 찾는 키에 매핑되어 있는 값을 반환하고 없다면 기본 값을 반환하는 메소드이다.  

 

 

<풀이 코드>

1.

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

 

2.

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
        
        HashMap<Integer, Integer> map = new HashMap<>();
        int arr[] = new int[2];
        
        for(int i = 0; i < nums.length; i++) {
            //if가 false이면 HashMap에 key-value 형태로 저장
            if(map.containsKey(target - nums[i])) {
                arr[1] = i;
                arr[0] = map.get(target - nums[i]);
            }
            map.put(nums[i], i);
        }
        return arr;
    }
}

 

 

<참고한 블로그>

https://hcr3066.tistory.com/26

https://codechacha.com/ko/java-map-hashmap/#3-hashmapget

Java - HashMap 사용 방법 및 예제