★two sum★
★제출했는데 틀렸던 문제★
https://leetcode.com/problems/two-sum/description/
문제 파악 [필수 작성]
문제이해
특정 인덱스의 두 원소를 더한 값이 Target 이다.
리스트와 target 이 주어지면 target 을 만들 수 있는
두 원소의 인덱스값을 리스트형태로 출력
제한 조건 확인
리스트최대길이 10^4 -> 이중포문 쓰면 안된다.
숫자의 범위는 10^10 -> int 범위 초과
아이디어
정렬후 투포인터 사용?
정렬한 후 r과 l을 절대값이 제일 작은 인덱스에 위치시킴
while 오른쪽 포인터와 왼쪽포인터가 0과 n-1 사이 일때
만약 현재값과 타겟값 같으면
두포인터 값 리스트형태로 리턴
현재 값이 target 값보다 크면 왼쪽 포인터 --
현재 값이 target 값보다 작으면 오른쪽 포인터 ++
시간복잡도
nlog(n)(정렬) + 2n(투포인터슬라이딩) -> nlog(n) < 10^4*log(2^14) -> 시간충분
자료구조
접근 방법 [필수 작성]
코드 구현 [필수 작성]
1차시도
절대값이 겹치는 케이스가 있음 [-1,1] 경우처럼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
new_nums = []
for index,num in enumerate(nums):
new_nums.append((num,index))
new_nums.sort()
min_abs = 10**9+1
min_abs_index = -1
#print(new_nums)
for index,elem in enumerate(new_nums):
if min_abs > abs(elem[0]):
min_abs = abs(elem[0])
min_abs_index = index
elif min_abs < abs(elem[0]):
break
l = min_abs_index
r = min_abs_index+1
while 0 <= l <= n-1 and 0 <= r <= n-1:
tmp = new_nums[l][0]+new_nums[r][0]
if tmp == target:
return[new_nums[l][1],new_nums[r][1]]
elif tmp > target:
l -= 1
elif tmp < target:
r += 12차시도
코드 복잡해지고 오히려 테케 더 틀림
반례
[2,3,3]
접근방법 자체가 잘못됐다고 생각하여 아예 갈아엎기
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
new_nums = []
for index,num in enumerate(nums):
new_nums.append((num,index))
new_nums.sort()
min_abs = 10**9+1
min_abs_index = -1
#print(new_nums)
for index,elem in enumerate(new_nums):
if min_abs > abs(elem[0]):
min_abs = abs(elem[0])
min_abs_index = index
elif min_abs < abs(elem[0]):
break
if min_abs_index - 1 > -1 and min_abs_index + 1 < n:
if abs(new_nums[min_abs_index-1] + new_nums[min_abs_index]) > abs(new_nums[min_abs_index] + new_nums[min_abs_index+1]):
l = min_abs_index
r = min_abs_index+1
else:
l = min_abs_index-1
r = min_abs_index
elif min_abs_index - 1 == -1:
l = min_abs_index
r = min_abs_index+1
elif min_abs_index + 1 == n:
l = min_abs_index-1
r = min_abs_index
while 0 <= l <= n-1 and 0 <= r <= n-1:
tmp = new_nums[l][0]+new_nums[r][0]
if tmp == target:
return[new_nums[l][1],new_nums[r][1]]
elif tmp > target:
l -= 1
elif tmp < target:
r += 1
while tmp != target:
tmp = new_nums[l][0]+new_nums[r][0]
if tmp == target:
return[new_nums[l][1],new_nums[r][1]]
elif tmp > target:
r -= 1
elif tmp < target:
l += 13차 시도 (아이디어 다시 생각 15분 소요)
아이디어 갈아엎기
해시테이블을 어떻게 사용할 수 있지?
문제를 보고 해시테이블을 떠올리는거 자체가 어렵다. 그냥 투포인터 문제라고 생각하기 쉬운데, 아니다.
[새로운 아이디어]
각 원소의 값을 key 값으로
각 원소의 인덱스값을 value 값으로 하여서
target 에서 각 key 값을 뺀 값이 dictionary 에 존재하는지 여부를 확인후
존재하면 해당 원소값과, 뺀값원소값의 인덱스를 리턴
다만, 같은 숫자는 두번 쓸 수 없으므로,
같은 숫자의 경우 갯수가 2개인지 확인해야함
[시간복잡도]
n(원소들을 딕셔너리에 저장) + n(원소유무탐색) = 2n
from collections import defaultdict
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dict = defaultdict(list) # key: 원소값 value: [index,index,...,]
for index,num in enumerate(nums):
num_dict[num].append(index)
for k in num_dict:
if target-k in num_dict:
if target-k == k:
if len(num_dict[k]) >= 2:
return [num_dict[k][0],num_dict[k][1]]
else:
return [num_dict[k][0],num_dict[target-k][0]]
배우게 된 점 [필수 작성]
key만 받아오고 싶을때
for k in dict_name:
print(k)pair로 받아오고 싶을 때
for k,v in dict_name.items():
print(k,v)투포인터를 초기화할때
리스트의 중간 위치에서 초기화하는 것과
양끝에서 초기화하고 점점 줄여나가는것은 큰 차이가 있다.
중간위치에 초기화하고 시작하면 가능한 경우를 탐색하지 못할수도 있지만,
중간위치에 초기화하고 시작하면 가능한 경우가 있으면 반드시 만나게 되어있다.
분할정복 및 그리디로 이해할 수도 있다.
해설코드
해설코드는 아예 for 문을 한개만 사용해서 구현했다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
#✅ 숫자와 숫자의 인덱스를 키, 밸류로 하는 빈 해시테이블을 만든다.
memo = {}
#✅ 숫자들을 순회한다.
for i, num in enumerate(nums):
#✅ 목표값을 만들기 위한 나머지 숫자를 구한다.
needed = target - num
#✅ 나머지 숫자가 해시테이블에 존재하면 그 수의 인덱스와 현재 인덱스를 반환한다.
if needed in memo:
return [memo[needed], i]
#✅ 아니라면 해시테이블에 숫자와 인덱스를 추가한다.
memo[num] = i질문 [ 필수 X ]
Q1.
솔직히 다시 풀더라도 해시맵을 떠올릴수 있을지 자신이 없습니다.
시간복잡도만 계산했을때는 투포인터로도 충분히 구현가능해보입니다. 하지만, 동일값(ex:[3,2,3]), 음수값이 포함되어있어, 투포인터로 구현하면 코너케이스를 처리하기 까다롭더라구요. 만약 투포인터를 활용해 푼다면 로직을 어떻게 설계할 수 있을까요? 수도코드를 작성해주실 수 있나요?
답변
다음과 같습니다.
기존 배열에 원소와 인덱스 값을 같이 저장하도록 수정 O(n)
원소값을 기준으로 정렬 O(nlogn)
배열의 좌측, 우측 위치를 투포인터로 설정
좌측 포인터와 우측 포인터가 만나지 않는 동안 반복 O(n)
두 포인터에 있는 원소 값의 합이 타겟인 경우
인덱스 값 반환
두 포인터에 있는 원소 값의 합이 타겟보다 작은 경우
좌측 포인터 +1
두 포인터에 있는 원소 값의 합이 타겟보다 큰 경우
우측 포인터 -1코드로 구현
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 기존 배열에 원소와 인덱스 값을 같이 저장하도록 수정 O(n)
nums_with_idx = []
for idx,num in enumerate(nums):
nums_with_idx.append((num,idx))
# 원소값을 기준으로 정렬 O(nlogn)
nums_with_idx.sort()
# 배열의 좌측, 우측 위치를 투포인터로 설정
l = 0
r = len(nums_with_idx)-1
# 좌측 포인터와 우측 포인터가 만나지 않는 동안 반복 O(n)
while l != r:
tmp = nums_with_idx[l][0] + nums_with_idx[r][0]
#print(nums_with_idx)
#print([nums_with_idx[l][1],nums_with_idx[r][1]])
if target == tmp:
return [nums_with_idx[l][1],nums_with_idx[r][1]]
elif target > tmp:
l += 1
else:
r -=1