본문 바로가기

SoftwareDo/알고리즘(코테)

leetcode 1. Two Sum

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

문제

int array와 특정 수를 입력받고, int array중 더해서 특정 수를 만들 수 있는 두 수의 index를 int array형태로 반환하라
1. array에는 답이 무조건 하나 있다.
2. 값이 중복될 수 있으나 중복된 값이 정답일 경우 무조건 중복된 값 둘 다 정답입니다.

풀이

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> indexMap = new HashMap<>();
    HashMap<Integer, Integer> indexMap2 = new HashMap<>();
    ArrayList<Integer> sortedList = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (indexMap.containsKey(num)) {
            indexMap2.put(num, i);
        } else {
            indexMap.put(num, i);
        }
        if (num <= target) {
            sortedList.add(Integer.valueOf(nums[i]));
        }
    }

    if (sortedList.size() == 2) {
        return buildAnswer(indexMap, indexMap2, sortedList.get(0), sortedList.get(1));
    }

    Collections.sort(sortedList);

    for (int i = 0; i <= (sortedList.size() / 2 + 1); i++) {
        int firstNum = sortedList.get(i);
        int secondNum = target - firstNum;
        for (int j = sortedList.size() - 1; j >= sortedList.size() / 2; j--) {
            if (secondNum == sortedList.get(j)) {
                return buildAnswer(indexMap, indexMap2, firstNum, secondNum);
            }
        }
    }
    return new int[]{0, 0};
}

public int[] buildAnswer(HashMap<Integer, Integer> indexMap, HashMap<Integer, Integer> indexMap2, int firstNum, int secondNum) {
    if (firstNum == secondNum) {
        return Arrays.stream(new int[]{indexMap.get(firstNum), indexMap2.get(secondNum)}).sorted().toArray();
    } else {
        return Arrays.stream(new int[]{indexMap.get(firstNum), indexMap.get(secondNum)}).sorted().toArray();
    }
}

처음 작성했던 코드입니다.
이 때 생각했던 것은, 
1. int array를 반대의 형태로 map을 만든다. (arr[index] = value -> map.get(value) = index)
2. 다만 중복 값이 있을 수 있어서 중복 값이 나올 경우를 위한 추가 map을 사용한다
3. 원본 배열을 정렬한다. (Arrays.sort()는 Quic Sort인 반면 Collections.sort()는 Tim Sort 입니다. 최악의 경우에도 NlogN을 보장할 수 있어서 array를 굳이 Collection, ArrayList로 변환하여 정렬했습니다.)
4. 정렬된 배열을 바탕으로 오름차 순으로 현재 수 와, 이 수가 정답이라면 이 배열에 있어야 하는 다른 수 (target - firstNum)를 내림차 순으로 찾고, 두 수가 존재한다면 indexMap에서 index를 찾고 리턴합니다.

이렇게 생각했던 이유는 정렬을 하여 이진탐색(?) 하여 더 빨리 데이터를 찾고 map을 활용해서 O(1)으로 index를 찾을 수 있다고 생각했습니다.
문제는 1. 이진 탐색을 제대로 구현하지 못 했습니다. 이렇게 할 거였으면, contains() 함수를 사용하는 것이 나았을 것 같습니다. 2. map을 두 개 사용했고, 정렬을 함으로써 비 효율적으로 메모리 및 연산을 사용했습니다.
3. 음수 생각을 못 했습니다.

진짜 풀이

사실, 문제 조건을 봤을 때 저렇게까지 복잡할 건 없었습니다.
1. map 에 map.get(value) = index map 하나는 필요합니다.
2. 원본 배열 x를 한 번 더 순회합니다. 이 때 indexMap.contains(target - nums[i]) 를 하고, 존재한다면 int[]{ indexMap.get(target - nums[i]), i } 를 반환합니다.

여기서 1이랑 2를 결합할 수 있습니다

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