two_sum dictionary 적용 관련 질문드립니다.
안녕하세요! two_sum 문제에 dictionary를 적용 관련하여 문의드리고자합니다.
강의 코드에서는 중복값이 존재 (ex : nums = [4,1,9,7], target = 14])일 때에 대해서는 해결이 되지 않았고, 해당 문제에 대해서는 해결을 하였습니다.
다만 leet code에서는 같은 값이 n번(n>=2) 들어갔을 경우 (ex : nums = [4,1,9,7,7], target = 14])에 대해서도 true를 반환해야할 것으로 보입니다.
파이썬 dictionary의 경우 nums = [4,1,9,7,7]로 dictionary를 생성하게되면 중복값은 key값 생성이 되지 않는 것으로 확인됩니다.
예를들어,
memo = {}
for index, v in enumerate(nums):
memo[v] = index
하게되면, { 4:0, 1:1, 9:2, 7:3, 7:4 }가 아닌 { 4:0, 1:1, 9:2, 7:4 }로 생성되는 것 같습니다. 이렇게 된다면 아래 조건식에서 판단이 어려운데 혹시 dictionary를 무조건 활용한다는 가정하에 가능한 방법(중복 key처리, 중복값에 대한 여부 저장 등(?))이 있을까요?
제가 문제에 대해 정확히 이해한것이 아닐 수 있어 만약 해당 상황에 대한 풀이는 필요하지 않다면 미리 양해말씀드립니다 ㅎㅎ..
답변 3
2
안녕하세요 빡빡이님.
중복이 있는 상황에 대한 올바른 답을 내는 코드는 노션에 올려드린 코드를 참고하셔도 됩니다.
또한, 이런경우 제 생각엔 value값으로 리스트를 생성해서 값을 넣는 형식으로 해도 해결가능할 것 같아보여요!!
2
안녕하세요. 같은 고민했던 기억이 있어 풀이 남겨두고 갑니다.
물론 저보다 빠르게 해결되는 풀이도 있지만, 딕셔너리로 간단하게 해결하는 방법이라도 참고하세요!
저는 인덱스로 value로 지정하여 담지 않고, 특정 원소가 있는 개수를 value로 사용하였습니다. 그리고 if 문을 추가하여 중복된 원소인지를 추가하는 로직을 통해 중복 키 여부를 판단하였습니당. 아래는 코드입니다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
_dict = {}
results = []
for number in nums:
if number in _dict :
_dict[number] += 1
else :
_dict[number] = 1
for index, number in enumerate(nums):
if target - number in _dict:
if target == number * 2 :
if _dict[number] >= 2 :
results.append(index)
else :
results.append(index)
return results
1
안녕하세요, 인프런 AI 인턴입니다.
two_sum 문제에서 중복값 처리에 대한 내용을 문의하셨는데요. 파이썬의 딕셔너리는 중복된 키를 가질 수 없기 때문에, 중복된 값을 처리하는데 어려움이 있습니다.
만약, 중복된 값에 대해서도 true를 반환하고 싶으시다면 딕셔너리 대신 리스트를 사용하는 방법이 있습니다. 예를 들어, 다음과 같이 리스트를 활용하실 수 있습니다.
nums = [4,1,9,7,7]
memo = []
for v in nums:
if target-v in memo:
return True
memo.append(v)
이렇게 리스트에 값을 추가하고, 타겟에서 현재 값의 차이가 리스트에 있는지 검사하여 중복된 값에 대해서도 True를 반환할 수 있습니다.
딕셔너리 대신 리스트를 사용하면 중복된 값을 처리할 수 있지만, 탐색 시간이 조금 더 오래 걸릴 수 있습니다. 따라서 문제의 조건과 자신의 상황에 맞게 적절한 방법을 선택하시면 됩니다.
더 많은 도움이 필요하시다면, 구체적인 문제 조건과 코드를 알려주시면 더 자세한 도움을 드릴 수 있을 것 같습니다. 감사합니다.
노션 공유 링크
0
85
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
75
2
최신 강의와 비교
0
83
2
Min Cost Climbing stairs 질문
0
75
2
노션 공유 부탁드립니다!
1
87
2
for 문에 sort 함수 를 사용하면
1
87
2
노션 공유 부탁드립니다.
0
102
2
디스코드가 올바르지 않다고 뜹니다..!
0
106
1
그래프
0
97
2
노션 공유
1
122
2
시간복잡도 질문
2
124
3
11강 질문
1
77
2
노션 공유 부탁드립니다
0
83
2
linkedList - BrowserHistory 코드 질문
0
75
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
166
1
라이브러리 사용
1
135
2
문제 교재는 따로 없는 거 맞나요?
1
201
2
LCA 관련해서 질문이 있습니다.
1
117
2
[Unique Paths] 완전탐색 / DP (후반부)
0
107
1
dp 계단오르기최소비용질문입니다.
0
107
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
162
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
121
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
202
1