[LeetCode] Two Sum 문제 풀이 (Array 이용, Python)

안녕하세요! 개발감자 박그냥입니다🥔

페이스북 개발자가 추천한 알고리즘 문제에서 가장 쉬운 1번 문제에 해당하는 Two Sum 문제 풀이입니다.

언어는 파이썬으로 진행하였습니다. 파이썬 문법을 제외하고 이 문제에 대한 아이디어 위주로 이야기해볼게요. 

 

 

알고리즘 문제에서 가장 중요한 것은 아이디어라고 생각합니다.

내가 가진 코딩 알고리즘을 가지고 어떻게 이 문제를 풀 것이냐?가 가장 중요한 관건인 것 같습니다.

이외에 구현하는 것은 그저 언어로 표현하는 과정이라고 생각합니다.

 

1. 문제 설명

1) 문제 이름
: Two Sum

2) 문제 난이도
: Easy

3) 문제 해석
: 주어진 정수 배열 nums와 정수 target이 있을 때, 두 숫자의 합이 주어진 target이 되도록 하는 두 숫자의 인덱스를 반환합니다. 각 입력값은 정확히 하나의 해결책을 가지며, 동일한 요소를 두 번 사용할 수 없습니다. 답은 어떤 순서로든 반환할 수 있습니다.

 

• 개발감자의 문제 해석 : 숫자가 담긴 리스트와 타겟 넘버를 하나 넘겨준다. 이 때, 타겟 넘버를 만들 수 있는 숫자 조합의 인덱스를 리스트로 나타내라!  순서는 상관없다!

 

덧붙이는 것에는 시간 복잡도를 N^2아래로 할 수 있는 알고리즘은 없는지가 써져있습니다.

여러분도 한 번 생각해볼까요? 어떻게 하면 시간 복잡도를 N^2이하로 간단하게 문제를 풀 수 있을까요?

아래의 제 아이디어를 참고해보세요.

 

 

2. 아이디어

저는 무조건 반복문을 한 번 쓸 것이다라고 생각했습니다.

한 번만 리스트를 훑으면서 타겟 번호를 만들 수 있는 조합을 찾아내면 그 즉시 반복문을 중지시키는 알고리즘 생각했습니다.

 

정리하자면

1) 리스트를 처음부터 끝까지 한 번 훑는다
2) 그 과정마다 타겟 번호를 만들 수 있는 숫자가 있는지 확인한다.
3) 있으면 output 리스트에 인덱스를 추가하고 반복문을 빠져나온다.

말이 쉽지 이걸 어떻게 하냐구요? 한 번 제 코드를 보실까요?

 

 

3. 풀이 설명

class Solution(object):
    def twoSum(self, nums, target):
        answer = []
        # 1차원 리스트이므로 N 복잡도로 구성함.
        for i in nums:
            # i 일때 다른 요소들 중 타겟을 만족시킬 수 있는 항목이 있는지 확인
            find = target - i
            # 지금 있는 요소를 뺀 리스트를 생성
            list_temp = nums[:]
            list_temp[list_temp.index(i)] = ""
            
            # 만족하는 항목이 있는 경우
            if find in list_temp:
                answer.append(nums.index(i))
                answer.append(list_temp.index(find))
                break
            # 없는 경우
            else : 
                continue


        return answer

 

제 코드입니다. 저는 무조건 문제를 풀기 전에 위의 아이디어를 주석으로 정리한 다음에 시작합니다.

위의 아이디어를 어떻게 실현했는지를 보면서 이해하시면 더 이해가 잘 될 겁니다.

1) 리스트를 처음부터 끝까지 한 번 훑는다
2) 그 과정마다 타겟 번호를 만들 수 있는 숫자가 있는지 확인한다.
3) 있으면 output 리스트에 인덱스를 추가하고 반복문을 빠져나온다.

 

1) 리스트를 처음부터 끝까지 한 번 훑는다

 answer = []
        # 1차원 리스트이므로 N 복잡도로 구성함.
        for i in nums:

 

answer = []  : 정답을 저장할 리스트

for i in nums : 반복문 한 번 돌리기

 

 

2) 그 과정마다 타겟 번호를 만들 수 있는 숫자가 있는지 확인한다.

# i 일때 다른 요소들 중 타겟을 만족시킬 수 있는 항목이 있는지 확인
find = target - i

 

 

지금 i를 가리키고 있을 때, 내가 찾아야 하는 숫자 find를 구합니다

 

# 지금 있는 요소를 뺀 리스트를 생성
list_temp = nums[:]
list_temp[list_temp.index(i)] = ""

 

지금 가리키고 있는 i 대신  ""을 추가한 리스트를 생성합니다. 

"" 를 추가한 이유는 현재 가리키고 있는 i를 제외시키기 위해서 입니다.

알고리즘이 숫자를 찾을 때 찾기 못하도록 정수가 아닌 문자 중 아무거나 넣어준 것입니다.

 

3) 있으면 output 리스트에 인덱스를 추가하고 반복문을 빠져나온다.

# 만족하는 항목이 있는 경우
if find in list_temp:
	answer.append(nums.index(i))
	answer.append(list_temp.index(find))
	break
# 없는 경우
else : 
	continue

 

i를 제외한 리스트인 list_temp에서 find 를 찾은 경우, find와 i에 해당하는 인덱스를 answer에 넣어주고 반복문 탈출!

없는 경우는 계속 진행하겠죠?

---

이렇게 문제 풀이를 완료해보았습니다. 문제를 푸는 분들에게 도움이 되었으면 좋겠습니다.

오랜만에 알고리즘 문제를 푸니, 두뇌 회전도 되면서 재미있네요ㅎㅎ

그럼 더 알찬 포스팅으로 돌아올게요. 개발감자였습니다.