참고
문제해설
NOTE
•
입력값 ⇒ 정수 배열과, 목표값
•
출력값 ⇒ 정수 배열에서 2개를 더해 목표값이 만족하는 인덱스
•
각 입력에는 정확히 하나의 솔루션이 있다고 가정하며, 동일한 요소를 사용하면 안된다.
문제 로직고민
NOTE
•
해당 문제의 풀이 방법을 고민해서 떠오른 생각이다.
◦
배열의 순서쌍을 모두 확인한다
▪
가장 단순하게 생각할 수 있는 방법이며, n^2의 시간복잡도가 생길것이다.
▪
배열의 길이가 최대 40,000인걸 감안하면 그렇게 좋은 판단같지 않다. 고려사항에도 n^2이외의 방법을 물어보고 있다.
◦
배열을 정렬한 후 Two Pointer 방식으로 접근한다.
▪
Arrays.sort()의 경우 n log n의 시간으로 정렬이 가능하다.
▪
Two Pointer의 경우 n의 시간으로 결과를 낼 수 있다.
▪
n log n + n의 경우 O(n log n)이므로 위의 방법보다 더 효율적이라고 생각한다.
▪
위의 방식대로 하면 문제가 생기는 요소가 있다.
▪
정렬된 배열은 기존의 배열과 요소의 순서가 달라지므로, 기존 배열을 복사한뒤 복사하고, 값을 찾은뒤, 검색하는 과정을 거쳐야한다.
▪
배열의 복사와, 2번의 검색은 3n의 시간복잡도가 추가로 생기지만, 그럼에도 n^2보다 좋다.
작성코드
NOTE
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] sorted_nums = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted_nums);
int start = 0;
int end = nums.length - 1;
int[] find = new int[2];
int[] result = new int[2];
while(start < end){
int sum = sorted_nums[start] + sorted_nums[end];
if(sum < target) start++;
else if(sum > target) end--;
else{
find[0] = sorted_nums[start];
find[1] = sorted_nums[end];
break;
}
}
for(int i=0; i<nums.length; i++){
if(nums[i] == find[0]){
result[0] = i;
break;
}
}
for(int i=nums.length-1; i >= 0; i--){
if(nums[i] == find[1]){
result[1] = i;
break;
}
}
return result;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int[] twoSum(int[] nums, int k)
{
Map<Integer, Integer> numIndices = new HashMap<>();
for (int i = 0; i < nums.length; i++)
{
int complement = k - nums[i];
if (numIndices.containsKey(complement))
return new int[]{numIndices.get(complement), i};
numIndices.put(nums[i], i);
}
return null;
}
}
Java
복사
메모리를 덜 쓰면서 해결
•
문제 유형이 HashTable이라 Map을 생각하긴 헀는데, 문제를 풀때 바로 떠오르는게 없었다.
•
이런 방식으로 접근이 가능하다는걸 배우게 되었다.