A. 문제설명
https://leetcode.com/problems/two-sum/
Two Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제에 대한 자세한 설명은 링크 참조
1. 배열 nums와 정수 target이 주어짐
2. nums 배열 내 두 값을 더해 수 target을 만드는 배열의 인덱스를 찾을 것
B. 접근법
1. Brute-force
먼저, 아주 단순하게 배열 내 모든 두 원소를 비교하며 Brute-force로 확인하는 방식이다. 이 경우 이중 for문에 의해 시간복잡도는 $O(n^{2})$이 된다.
2. HashTable
1번의 구현을 HashTable의 사용으로 최적화할 수 있다. HashTable을 만드는 시간복잡도 비용은 $O(n)$이지만, Lookup 비용은 $O(1)$이기 때문에 훨씬 절약할 수 있다. HashTable의 공간복잡도 비용은 $O(n)$이 된다.
3. One-pass HashTable
2번을 다시 한번 최적화하여, 한번의 Iteration에서 HashTable을 만듦과 동시에 Lookup을 하도록 할 수 있다. 2번에서는 HashTable을 만들고($O(n)$), 그 다음 Lookup을 위한 Iteration($O(n)$)을 하여 총 비용이 $O(2n)$이 되겠지만, 이를 한번의 Iteration으로 $O(n)$에 처리한다.
C. 결과
테이블 행 순으로 위에서부터 3번(One-pass HashTable) -> 2번(HashTable) ->1번(Brute-force)이다. 3번의 경우 Runtime을 20ms까지 줄일 수 있었다.
D. 내 코드