Two Sum 문제: 배열에서 두 숫자의 합으로 목표 값 찾기

Two Sum 문제: 배열에서 두 숫자의 합으로 목표 값 찾기

• 주어진 배열에서 두 숫자를 선택하여 더했을 때 특정 목표 값(target)이 되는 숫자 쌍의 인덱스를 반환하는 문제입니다.

• 단, 배열에는 중복된 값이 없고, 한 쌍의 답만 존재한다고 가정합니다.

---

예제 1

• 배열: [2, 7, 11, 15], 목표 값(target): 9
  • 2 + 7 = 9 이므로 반환값은 [0, 1]

예제 2

• 배열: [1, 5, 3, 6], 목표 값(target): 8
  • 5 + 3 = 8 이므로 반환값은 [1, 2]

예제 3

• 배열: [4, 2, 10, -3], 목표 값(target): 7
  • 10 + (-3) = 7 이므로 반환값은 [2, 3]

---

조건:

• 입력 배열은 정렬되지 않았을 수 있습니다.
• 시간 복잡도를 최소화하는 효율적인 알고리즘을 구현하세요.

---

• 다음은 주어진 문제를 효율적으로 해결하는 파이썬 코드입니다:

python

def two_sum(nums, target):
    # 딕셔너리를 사용하여 값을 기록
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target - num  # 목표 값에서 현재 숫자를 뺀 값
        if complement in num_to_index:  # 보완 숫자가 이미 기록된 경우
            return [num_to_index[complement], i]
        num_to_index[num] = i  # 현재 숫자와 인덱스를 기록
    return []  # 답이 없으면 빈 리스트 반환 (문제 조건상 필요 없음)

# 예제 실행
nums1 = [2, 7, 11, 15]
target1 = 9
print(two_sum(nums1, target1))  # 출력: [0, 1]

nums2 = [1, 5, 3, 6]
target2 = 8
print(two_sum(nums2, target2))  # 출력: [1, 2]

nums3 = [4, 2, 10, -3]
target3 = 7
print(two_sum(nums3, target3))  # 출력: [2, 3]

---

코드 설명

1. 딕셔너리 사용:

   • num_to_index 딕셔너리는 배열의 숫자와 그 숫자의 인덱스를 기록합니다.
   • 딕셔너리를 사용하면 보완 숫자를 상수 시간에 탐색할 수 있어 효율적입니다.

2. 반복문:

   • 배열의 각 숫자를 순회하며 보완 숫자(target - num)가 이미 기록되어 있는지 확인합니다.
   • 기록되어 있다면, 두 숫자의 인덱스를 반환합니다.

3. 시간 복잡도:

   • 딕셔너리를 사용해 탐색과 삽입이 O(1) 시간에 이루어지므로, 전체 알고리즘의 시간 복잡도는 O(n) 입니다.

view raw Two.Sum.ko.md hosted with ❤ by GitHub