인프런 커뮤니티 질문&답변

으수님의 프로필 이미지
으수

작성한 질문수

코딩테스트 [ ALL IN ONE ]

[코테 적용] 👉 [1번 문제] key in (후반부)

two_sum dictionary 적용 관련 질문드립니다.

해결된 질문

작성

·

399

1

안녕하세요! 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를 반환할 수 있습니다.

딕셔너리 대신 리스트를 사용하면 중복된 값을 처리할 수 있지만, 탐색 시간이 조금 더 오래 걸릴 수 있습니다. 따라서 문제의 조건과 자신의 상황에 맞게 적절한 방법을 선택하시면 됩니다.

더 많은 도움이 필요하시다면, 구체적인 문제 조건과 코드를 알려주시면 더 자세한 도움을 드릴 수 있을 것 같습니다. 감사합니다.

으수님의 프로필 이미지
으수

작성한 질문수

질문하기