문제) 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.
https://leetcode.com/problems/two-sum/description/
풀이)
1. 브루트포스로 풀기
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1) :
for j in range(i+1 , len(nums)) :
if nums[i] + nums[j] == target :
return [i,j]
2. in을 이용한 탐색
모든 조합을 비교하지 않고, 정답(타겟)에서 첫 번째 값을 뺸 값 (target - n) 이 존재하는 지 탐색하는 문제로 변경하여 풀이할 수 있다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[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 )
여기서 더 나아가 수를 키로 하고 인덱스는 값으로 바꿔서 딕셔너리로 저장하면 키를 조회해서 정답을 즉시 찾아낼 수 있다
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_map = {}
for i , n in enumerate(nums) :
nums_map[n] = i
for i , n in enumerate(nums) :
# 만일 target - n 이 nums 에 포함되어 있고 해당 인덱스가 현재 인덱스와 동일하지 않은 경우
if target - n in nums and i != nums_map[target-n] :
return [i , nums_map[target-n]]
🤔이 문제를 투 포인터로 풀 수 있을까?
입력값인 nums는 정렬된 상태가 아니다. 투 포인터를 이용해 풀이를 하기 위해서는 정렬이 필요하다. 하지만 이렇게 하면 인덱스는 엉망이 된다. 이처럼 값이 아닌 인덱스를 찾아내는 문제는 정렬을 통해 인덱스를 섞어버리면 곤란하다.
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[LeetCode] - 배열 파티션 I (0) | 2023.11.14 |
---|---|
[LeetCode] - 세 수의 합 (0) | 2023.11.14 |
[프로그래머스] Lv1 문제풀이 (1) | 2023.10.09 |
[프로그래머스] Lv1 문제풀이 (0) | 2023.10.09 |
[백준] 1937번 욕심쟁이판다 - 파이썬 (0) | 2023.10.06 |