리트코드 - 1. Two Sum

리트코드 - 1. Two Sum

출처 - https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums와 정수 target이 있을 때, 두 숫자를 선택하여 그 합이 target이 되도록 하는 두 숫자의 인덱스를 반환하세요.

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

어떤 순서로든 답을 반환해도 됩니다.

 

의사코드

해쉬테이블 hashTable 생성 answer 배열 생성 반복문 시작[nums 배열 순회, i는 +1씩]     rest = target - nums[i]        if (hashTable이 key값으로 rest를 가지면)         answer[0] = i         answer[1] = hashTable의 key=rest인 value 가져옴         break     hashTable에 key=nums[i] value=i 대입 반복문 종료

 

풀이코드

import java.util.Hashtable;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Hashtable<Integer, Integer> hashTable = new Hashtable<>();
        int[] answer = new int[2];

        for (int i = 0; i < nums.length; i++) {
            int rest = target - nums[i];

            if (hashTable.containsKey(rest)) {
                answer[0] = i;
                answer[1] = hashTable.get(rest);
                break;
            }

            hashTable.put(nums[i], i);
        }

        return answer;
    }
}

코드설명

해쉬테이블을 이용하여 문제를 풀었다. 먼저 해쉬테이블과 크기 2짜리 answer 배열을 만든다.

배열을 순회하는데 target이 주어지므로 나머지(rest) 값을 구한다.

 

해쉬테이블이 key값으로 rest를 가지면 현재 인덱스를 answer 배열 첫번째에, 그리고 해쉬테이블에서 key=rest인 value를 answer 배열 두번째에 저장한다.

 

만약 해쉬테이블이 key값 중에 rest가 없으면 key= 현재 배열 값, value = 현재인덱스 를 저장한다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (답이 있다고 가정할 경우 최악의 경우 n-1개만큼)

 

문제를 풀며 생각한 흐름과 배운 점

정렬이 안되어 있는 배열이라 투포인터를 쓰기 어려웠다.

또 해쉬테이블을 이용하는 방법을 써보려고 했는데 key값을 인덱스로 쓰기도 애매하고, 그렇다고 key가 숫자로만 있어도 Iterator를 써야 해서 조금 더 생각해봤다.

 

나머지 값을 미리 계산해서 이 값이 테이블에 있는지 없는지 분기로 나누니 생각보다 코드가 간단해졌다.

처음으로 한 번만에 푼 문제인데 아이디어를 잘 떠올린게 운이 좋았던 것 같다.

사실은 이 문제 풀기 전에 화장실을 들락날락(?) 할 때 재미로 알고리즘 입문 java 책을 보고 있는데 거기서 재귀 알고리즘을 봤었다.

재귀 알고리즘은 아니지만 if문을 짠 게 약간 비슷한 느낌으로 코드가 작성된 것 같다.

 

해쉬테이블과 해쉬맵?

그런데 생각해보니 해쉬테이블 구조는 이번에 처음 사용해본 것 같다.

보통 Map을 사용하면서 HashMap을 주로 쓰지 HashTable을 쓸 기회가 없었기 때문이다.

오라클 문서를 보면 HashTable은 인터페이스 Map을 구현한 클래스이다.

 

[HashTable 특징]

메소드가 동기화되어 멀티쓰레드 환경을 지원

key와 value 값에 null을 허용하지 않음

동기화 오버헤드로인해 성능 저하가 있음

해쉬값이 중복되면 오픈 어드레싱(Open Addressing) 방식을 사용. 계산방법은 Linear Probing, Quadratic Probing

 

[HashMap 특징]

싱글쓰레드만 지원

key와 value값 모두 null을 허용

AbstractMap클래스를 상속받음

해쉬값이 중복되면 Separate Chaining 방식을 사용. linkedList를 이용해서 처리

 

크기가 커지면 Open Addressing보다는 Separate Chaining방식이 더 효율적이라고 한다.

해쉬값 중복에 대한 처리를 개선한 것이 HashMap이고, HashTable을 지원하긴 하지만

HashMap에서 멀티쓰레드를 지원하는 ConcurrentHashMap 등도 있다고하니 앞으로는 HashMap을 잘 사용하도록 해야겠다.

 

다른코드

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
    }
}

역시 해쉬맵을 사용하고 있다.

리턴 값으로 곧바로 배열을 생성해서 내 코드보다 조금 더 간결하다.

 

 

정리

key-value 타입을 어떻게 적용할지 로직을 짜는 방법

HashTable 대신 HashMap 사용하기

 

[참고]

Java HashMap은 어떻게 동작하는가?

해시(Hash)와 해시 충돌 해결 방법