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;
}
'SoftwareDo > 알고리즘(코테)' 카테고리의 다른 글
leetcode 12. IntegerToRoman (Java) (0) | 2024.05.06 |
---|---|
leetcode 13. RomanToInteger (0) | 2024.05.06 |
leetcode 9. PalindromeNumber 풀이 (0) | 2024.05.05 |
leetcode 606. ConstructStringFromBinaryTree 풀이 (재귀함수) (0) | 2024.05.04 |
leetcode 1903. LargestOddNumberInString 오답노트 (0) | 2024.05.03 |