[Python algorithm interview] enumerate(), 배열의 사용

파이썬 알고리즘 인터뷰의 2020ver을 리뷰하고 있습니다.

 

7. 두 수의 합

 

최근들어 알게된 사실이지만 현재까지 소개한 문제는 모두 해외의 알고리즘 풀이 사이트

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - The World's Leading Online Programming Learning Platform

에서 소개된 문제였습니다. 필자도 처음 들어가보았습니다.

영어의 장벽만 넘을 수 있다면 디자인도 깔끔하고, 특히 백준이나 프로그래머스에 비해

시간 복잡도 체크에서 큰 강점을 갖고 있는 것으로 보입니다. 알고리즘 풀이 영상 강의도 제공합니다만

아쉽게도 explore에서 대다수의 강의를 듣기 위해선 유료 제품을 구해야 하는 부분이 아쉽네요.

 

 

이번의 경우에도 같은 풀이에 대해서 더 빨리 풀수 있도록 challenge를 부과하는 화면도 보여줍니다.

 

 

두수의 합(Add two numbers)는 leet code에서도 첫번째로 소개하고 있는 문제입니다.

문제를 살펴보겠습니다.

 

🎈문제

 

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라

 

🔑입력 예제

 

입력

nums = [2, 7, 11, 15]
target = 9

출력

[0, 1]

 

 

🛴 풀이법. ep1 in을 이용한 탐색

해답

#  in을 이용한 탐색
def twosum(nums: list[int], target : int):
    for i, n in enumerate(nums):
        complement = target - n
        
        if complement in nums[i + 1:]:
            return nums.index(n), nums[i +1:].index(complement) + (i+1)

 

언뜻 보면 떠올리기 쉽지 않은 풀이일 수 있습니다.

 

숫자 a와 숫자 b를 구해서 target이라는 숫자가 나온다는 개념에 집중하는 것이 아니라,

target에서 어떤 숫자를 빼면 숫자 b가 나올까? 정도로 생각해 볼 수 있습니다.

 

complement = target - n

 

이때 사용하는 것이 for문을 튜플처럼 만들어주는 내장함수, enumerate()입니다.

enumerate 함수는 기본적으로 인덱스와 원소로 이루어진 튜플을 만들어 주는데요?

그래서 원소를 2개를 받는것도 가능합니다.

 

# twosum은 풀이용 함수 정의
def twosum(nums: list[int], target : int):
    for i, n in enumerate(nums):
        print(i,n)

 

이러할 경우 i에는 인덱스 값이, n에는 nums리스트의 원소가 쌓이게 됩니다.

nums에 [2, 7, 11, 15]를 넣고, target은 9를 넣어보겠습니다.

 

twosum([2, 7, 11, 15], 9)

0 2
1 7
2 11
3 15

 

이런 식입니다.

편리하게 인덱스값을 구할 수 있겠네요.

 

이제 target에서 n을 뺀 값을 넣어보겠습니다.

 

def twosum(nums: list[int], target : int):
    for i, n in enumerate(nums):
        complement = target - n

 

이제 in 함수를 사용해서 complement안에 해당 숫자가 들어가 있는지 검증해줍니다.

 

#  in을 이용한 탐색
def twosum(nums: list[int], target : int):
    for i, n in enumerate(nums):
        complement = target - n
        
        if complement in nums[i + 1:]:
            return nums.index(n), nums[i +1:].index(complement) + (i+1)

 

리트코드 결과

 

🛵 풀이법. ep2 첫번째 수를 뺀 결과키 조회(dictionary)

 

위 풀이법도 있지만 이는 탐색을 이용한 방법으로, 개선의 여지가 보입니다.

일종의 딕셔너리를 쓰는 것이죠.

 

def twosum(nums: list[int], target:int):
    nums_map = {}

 

이러면 target에서 첫번째 수를 빼면 그 두번째 수를 바로 알아낼 수 있습니다.

 

def twosum(nums: list[int], target:int):
    nums_map = {}
    for i, n in enumerate(nums):
        nums_map[n] = i
    for i, n in enumerate(nums):
        if target - n in nums_map and i != nums_map[target - n]:
            return nums.index(n), nums_map[target - n]

 

nums_map을 프린트하든, 프린트하지 않든 결과는 똑같이 나옵니다.

 

def twosum(nums: list[int], target:int):
    nums_map = {}
    for i, n in enumerate(nums):
        nums_map[n] = i
    for i, n in enumerate(nums):
        if target - n in nums_map and i != nums_map[target - n]:
            return nums.index(n), nums_map[target - n]
    print(nums_map)

 

🛵 풀이법. ep3 조회 구조 개선(dictionary)

 

본문에서는 이 방법의 효율을 또 끌어 올리기 위해서  for문을 하나만 사용하는 방법도 소개하고 있습니다.

그렇지만 직관적으로 이 풀이를 바로 떠올리는 것은 거의 불가능에 가깝다는 생각이 듭니다.

 

 

# for 문을 하나만 사용한 경우
# 단번에 떠올리기는 어렵지 않을까?
def twosum(nums : list[int], target : int):
    nums_map = {}
    for i, n in enumerate(nums):
        if target - n in nums_map:
            return [nums_map[target - n], i]
        nums_map[n] = i

 

좋은 접근임에는 틀림 없습니다.

 

 

시간은 약간 줄어들었네요.

 

그 이외에도, 여기서는 생략하였지만 Brute force를 이용한 방법과 다른 프로그래밍 언어인 Go를

사용한 방식도 있었습니다만 브루트 포스는 일일히 대입하는 방식이고, Go는 사실상 언어를 하나 더

추가하는 셈이기 때문에 여기에는 남기지 않겠습니다.

 

완료.