[Top Interview Questions] #1. Two Sum

정답)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 딕셔너리를 사용해 필요한 정수와 그 인덱스 값을 저장.
        # 첨에는 배열의 0번째 정수와 그 인덱스 0을 저장.
        numDic = {nums[0] : 0}

        # 1부터 배열의 끝까지 선형검색한다
        for i in range(1, len(nums)):
            # 선형검색하면서 짝을 이룰 정수를 구한다
            pair = target - nums[i]

            # 만약 짝이 존재한다면
            if pair in numDic:
                # 그 짝의 인덱스와 선형검색하던 정수의 인덱스를 리턴.
                return numDic[pair], i

            # 짝이 존재하지 않는다면 딕셔너리에 현재 정수와 인덱스를 저장.
            numDic[nums[i]] = i

문제)

정수로 이루어진 배열(nums)과 타겟으로 하는 정수(target)가 주어졌을 때, 타겟을 합으로 하는 두 정수의 인덱스를 리턴하시오.

인풋값엔 무조건 하나의 정답이 존재하고, 한개의 원소를 두 번 사용할 수 없습니다. 인덱스의 순서는 바뀌어도 됩니다.

 

예시 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

예시 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

 

예시 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

문제링크

설명)

먼저 문제에서 구해야되는 정수의 인덱스값을 요구하기 때문에 정수 값을 비교하면서 그 정수의 인덱스 값을 동시에 알 수 있는 방법이 필요합니다. 그래서 dictionary를 쓰게 될 경우 더해야되는 정수와 그 정수의 인덱스값을 key와 value로 묶어서 저장할 수 있기 때문에 dictionary를 사용했습니다.

 

딕셔너리에 미리 0번째 정수와 0을 저장한 이유는 배열엔 무조건 정답이 존재한다고 되어있기 때문에 2개 이상의 정수가 존재합니다. 그러므로 무조건 0번째 정수가 존재하며 다음 단계에서 1번째 정수와 바로 비교하기 위해서입니다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDic = {nums[0] : 0}

 

0번째 정수를 저장했기 때문에 여기서 for 문은 1부터 시작하게 됩니다. 편의성을 위해 pair라는 변수에 구해야 되는 정수의 값을 저장해 줍니다. 예시 1을 참고하자면 pair에 9 - 7을 저장합니다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDic = {nums[0] : 0}

    for i in range(1, len(nums)):
        pair = target - nums[i]

 

그렇게 저장된 pair가 딕셔너리에 존재하는지 확인합니다. numDic에는 key가 정수, value가 정수의 인덱스값입니다. 그러므로 딕셔너리에 정수가 존재하는지 확인하려면 numDic의 key에 정수가 존재하는지 확인하면 되겠죠? key를 찾는 방법은 간단히 "if pair in numDic" 으로 확인하면 됩니다. 그렇게 pair가 numDic에 존재한다면 그 pair의 인덱스값 (즉, numDic[pair])과 현재 정수의 인덱스값 (즉, 현재 i)를 리턴하면 됩니다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDic = {nums[0] : 0}

    for i in range(1, len(nums)):
        pair = target - nums[i]

        if pair in numDic:
            return numDic[pair], i

 

만약 numDic의 key에 pair가 존재하지 않는다면 딕셔너리에 현재 nums의 정수와 그 정수의 인덱스값을 key, value로 밑과 같이 저장하면 됩니다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDic = {nums[0] : 0}

    for i in range(1, len(nums)):
        pair = target - nums[i]

        if pair in numDic:
            return numDic[pair], i

        numDic[nums[i]] = i

예시) 예시 2를 사용하여 풀어보겠습니다.

nums = [3, 2, 4], target = 6

 

numDic에 {3 : 0} 이 저장됩니다. (3은 0번째 정수로 key, 0은 3의 인덱스값으로 value로 저장됩니다.)

 

(i = 1)

pair = 6 - 2 = 4

현재 numDic에는 {3 : 0} 으로 이루어져 있습니다. 4가 numDic에 없으므로 현재 정수와 인덱스값을 새로 저장합니다.

numDic이 {3 : 0, 2 : 1} 으로 업데이트됩니다.

 

(i=2)

pair = 6 - 4 = 2

현재 numDic에 2가 존재합니다! 그러므로 numDic[2]와 i를 리턴합니다. numDic[2]의 val값은 1, i는 2입니다.

그러므로 output은 (1, 2)가 됩니다.

결론)

이 방법은 배열을 선형검색함으로써 n개만큼의 원소를 검색할 수 있음으로 시간 복잡도는 O(n)이 될 것입니다.

그리고 딕셔너리를 사용하기 때문에 최악의 상황엔 n-1개만큼의 저장공간이 필요함으로 공간 복잡도 또한 O(n)이 될 것입니다.

 

풀이과정에 질문이나 잘못된 부분이 있으면 알려주세요 :)