Two Sum 문제 질문드립니다.

코딩테스트 [ ALL IN ONE ]

작성

275

시간복잡도 O(nlogn)으로 코드를 작성하는 중인데,

코드 맨 마지막 줄에서 index 함수를 썼을 때, 중복값은 제일 맨 앞 인덱스만 반환하더라구요.

다른 해결 방법이 있을지 궁금합니다!

nums = [3,3], target = 6
Output: [0,1]

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    array = sorted(nums)
    left = 0
    right = len(nums)-1
    while left < right:
      if array[left] + array[right] > target:
        right -= 1
      elif array[left] + array[right] < target:
        left -= 1
      elif array[left] + array[right] == target:
        return [nums.index(array[left]), nums.index(array[right])] # 이 부분

알고리즘 algorithm 코테 준비 같이 해요! python

답변 1

개발남노씨

지식공유자

안녕하세요 배추님. Discord를 참고하셔도 좋을 것 같아요.

https://discord.com/channels/941959559759679559/1065795296518471680

nums.index()를 사용하셨군요. 좋은 접근같아요. 근데, 이 문제에서는 중복된 숫자 상황에서 우리가 원하는대로 결과값이 안나오죠. 음..

저는 일단 아래와 같이 풀이했습니다.

def twoSum(self, nums, target):

    origin_indices = {}

    for idx, val in enumerate(nums):
        if val in origin_indices:
            origin_indices[val].append(idx)
        else:
            origin_indices[val] = [idx]

    nums.sort()

    l, r = 0, len(nums)-1

    while l < r:
        if target > (nums[l] + nums[r]):
            l += 1
        elif target < (nums[l] + nums[r]):
            r -= 1
        else:
            return [origin_indices[nums[l]][0], origin_indices[nums[r]][-1]]

이 코드에서 좀 더 개선할 사항이 있다면 피드백 해주세요 ㅎㅎ

list.index()를 활용하는 방법으로는 해결법이 떠오르지 않네요 ㅜ

개선된 코드는 디스코드에서도 공유해 주세요 :)

배추

질문자

네 참고하겠습니다! 감사합니다 :)

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

Two Sum 문제 질문드립니다.