Table of Contents
문제
원문 보기 : [LeetCode] 1. Two Sum
정수 배열 nums와 정수 target이 주어진다. 더해서 target이 되는 두 숫자의 인덱스를 반환하면 된다.
모든 입력은 정확히 하나의 답만을 가지며, 같은 원소를 중복 사용하지 않는다.
정답의 순서는 상관 없다.
조건(Constraints):
1
2
3
4
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
예제
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3
Input: nums = [3,3], target = 6
Output: [0,1]
계획
- 내가 이해한 것
중복하지 않게 2개를 뽑아 더해서 원하는 숫자가 나오면 된다. 투 포인터로 탐색하면 되는 거 아냐? - 실행과 결과
투 포인터를 사용하는 코드로 제출해서 바로 통과했으나, 내 코드의 실행 시간이 상위 50%도 안 나오고 대부분 답안이 훨씬 상위에 몰려 있는 게 수상했음. - 문제 태그 확인
나는 당연히 투 포인터가 있지 않을까 생각했는데, 예상외로 투 포인터는 없고 해시 테이블이 있었다. 이게 왜 있어? - 상위 답안 참고
실행 시간 기준 최상위 답안 몇 개를 봤다.
인덱스를 잘 이용해서 투 포인터를 사용한 코드는 서로 반대 방향으로 동시에 비교한 것 같다는 어렴풋한 이해는 가능했지만 그래서 정확히 뭘 하고, 어째서 그렇게 빨리 나오는지는 이해하지 못했다. 해시 테이블과의 연관성도 모르겠다.(map컨테이너는 알지만 해시 테이블이라는 자료구조의 이론을 아는 건 아님)
다른 답안을 찾아보니unordered_map을 사용한 답이 있었다. 게다가 주석도 자세했다. 좋은 참고가 되었다. 배열의 앞에서부터 순회하며map에 값을 넣는데,target과 현재 탐색중인 수의 차이를key로 만들어map에 그 값이 존재하는지 확인하고, 존재한다면 바로 답으로 반환하고 그렇지 않다면map에 값과 인덱스를 추가한다.map이 내부적으로 트리를 이용한다는 건 알고 있었는데,unodered_map은 이번에 처음 봐서 자료구조를 찾아보니 해시 테이블로 구현된다고 한다. 그래서 태그가 해시 테이블이었다..
풀이
1. 투 포인터
Runtime : 360 ms
Memory : 10.2 MB
리뷰
- 처음엔 답안 벡터를 만들고, 답을 찾았는지 표시하는
bool변수를 만들어서 반복문을 모두 빠져나간 다음 답안을 반환하게 했는데, 다른 답안을 참고해보니 꼭 그렇게 할 필요가 없어서 반복문 중간에 바로 답안을 반환하게 고쳤다. - 반복문 바깥의 답안 반환 부분에서 다른 것 없이
{}만 써서 제출해도 통과가 되는 것 같던데, 메소드의 반환 형식이vector<int>로 정해져 있어서 가능한 것 같다. 마찬가지로 반복문 내부 답안도{i, j}로 바로 반환할 수 있는데, 이번에는 내가 알아볼 수 있게 써두려고 그렇게 쓰지 않았다. 다음에는 참고해서 쓸 수 있을지도? - 어차피 O(n2)이지만 적어도 조금이라도 시간을 줄여보려고
i와j가 겹치지 않게 반복문을 썼다. 물론 큰 의미는 없을 것이다..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
return vector<int>{i, j};
}
}
}
return vector<int>{};
}
};
2. unodered_map
* 샘플 답안 중에 본 건데, 이 답안의 원본 링크를 알 수가 없어 출처는 표기하지 못했다.
Runtime : 7 ms
리뷰
unordered_map의 존재를 처음 알았다.map은Red-Black Tree로,unordered_map은Hash Table로 구현된다고 한다.- (적어도 이 문제에 한해서는) 투 포인터 탐색과 같은 답을 낼 수 있으면서도 훨씬 빠른 풀이 방법을 배웠다. 알고리즘은 나날이 새롭다..
풀이
unordered_map을 준비하고, 하나의 반복문으로 주어진 배열을 앞에서부터 순회한다.- 목표하는 값과 현재 검사하는 수의 차를 구한다. 이를
toFind라 한다. toFind가 맵에 있는지, 그리고toFind의 인덱스가 현재 검사하는 수와 다른지 확인한다.- 만약 2번을 통과했다면
toFind의 인덱스와 현재 검사하는 수의 조합이 답이다. 바로 반환한다. - 2번을 통과하지 못했다면 답이 아니고, 현재 검사한 수를 맵에 추가한다.
- 목표하는 값과 현재 검사하는 수의 차를 구한다. 이를
- 반복문이 끝나면 답을 찾지 못한 것이므로 빈 벡터를 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// Result vector to hold "Two Sum" equals to "Target"
vector<int> result;
// We need to return the "index" of the "Two Nums" results in "Target"
unordered_map<int,int> indexMap;
// Cannot have the "auto" iterator variable, since we are interested in "index", not the actual value.
for (int i = 0; i < nums.size(); i++) {
// Check if the "target-current" value already exist in the IndexMap.
int toFind = target - nums[i];
if (indexMap.find(toFind) != indexMap.end() && // "IndexMap" has the entry
i != indexMap[toFind]) { // AND we are not working on the same index
/* Another corner use-case: Target-10, Current-5 toFind-5 */
result.push_back(i);
result.push_back(indexMap[toFind]);
return result;
}
indexMap[nums[i]] = i;
}
// Return empty vector if there is NO "Two Sum" equal to "Target"
return {};
}
};