[IT/코딩테스트] KB ITYL 알고리즘 해시맵 예제 : Two Sum (leetcode)
▶ 문제 설명
정수 배열 nums와 정수 target이 주어졌을 때, 배열에서 두 수를 골라 더했을 때 그 합이 target이 되는 두 수의 인덱스를 반환하세요.
- 각 입력에 대해 정답은 오직 하나만 존재합니다.
- 같은 요소를 두 번 사용할 수는 없습니다.
- 반환하는 인덱스의 순서는 상관없습니다.
▶ 제한 사항
1) 2 ≤ nums.length ≤ 10⁴
2) -10⁹ ≤ nums[i] ≤ 10⁹
3) -10⁹ ≤ target ≤ 10⁹
4) 정답은 무조건 하나 존재
▶ 입출력 예시
| 번호 | 입력 | 출력 | 설명 |
| 예시 1 | nums = [2, 7, 11, 15], target = 9 | [0, 1] | nums[0] + nums[1] = 2 + 7 = 9 |
| 예시 2 | nums = [3, 2, 4], target = 6 | [1, 2] | |
| 예시 3 | nums = [3, 3], target = 6 | [0, 1] |
✅ [방법 1] 브루트포스 방식 (이중 for문)
▶ 문제 정리
⚈ 문제 유형: 배열 탐색, 완전 탐색(Brute Force)
⚈ 문제 파악 + 접근 방법:
배열 내의 모든 두 수를 더해보며 target과 같은지 확인하는 방식
→ 시간복잡도는 O(n²)로 비효율적이지만, 로직 자체는 단순하며 직관적으로 이해할 수 있다.
⚈ 풀이 로직 요약:
1) nums 배열에서 모든 두 인덱스 쌍(i, j)을 탐색 (단, i < j)
2) nums[i] + nums[j] == target이면 해당 인덱스를 반환
3) 정답은 반드시 존재하므로, 조건이 만족되면 바로 return
솔루션 코드
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
코드 분석 결과
깨달은 점 / 핵심:
1) 모든 경우를 시도하므로 실패 확률은 없지만, 비효율적이다.
2) 시간복잡도 O(n²)로, 배열의 크기가 커질수록 성능 저하가 심하다.
3) 가장 기본적인 탐색 로직을 연습하고 이해하는 데 적합하다.
✅ [방법 2] 해시맵(Hash Map)을 활용한 방식
▶ 문제 정리
⚈ 문제 유형: 배열 탐색 + 해시 테이블
⚈ 문제 파악 + 접근 방법:
이미 탐색한 값들을 해시맵에 저장해두고, 현재 값의 보충값(target - 현재 값)이 해시맵에 존재하는지를 매번 확인
→ 빠르게 정답을 도출
⚈ 풀이 로직 요약:
1) 해시맵 num_to_index를 생성 (key: 수, value: 인덱스)
2) nums 배열을 순회하면서, 각 원소에 대해 target - num이 해시맵에 있는지 확인
3) 있다면 현재 인덱스와 해시맵에서 찾은 인덱스를 반환
4) 없으면 현재 숫자와 인덱스를 해시맵에 저장
5) 시간복잡도는 O(n)
솔루션 코드
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
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
** enumerate(iterable, start=0)
리스트, 튜플, 문자열처럼 순서가 있는(iterable한) 객체를 반복할 때, 인덱스(index)와 값(value)을 동시에 꺼낼 수 있게 해주는 내장 함수
- iterable : 리스트나 문자열처럼 반복 가능한 객체
- start : 인덱스를 시작할 숫자 (기본값은 0)
<예시>
fruits = ["apple", "banana", "cherry"]
for i, fruit in enumerate(fruits):
print(i, fruit)
# 결과
0 apple
1 banana
2 cherry
코드 분석 결과
깨달은 점 / 핵심:
1) 해시맵은 특정 값이 존재하는지를 O(1)에 판단할 수 있으므로 매우 효율적이다.
2) 이미 탐색한 값을 저장하여 중복 탐색을 피하는 전형적인 최적화 패턴이다.
3) 시간복잡도는 O(n), 공간복잡도는 O(n)이다.
4) 해시맵(딕셔너리)은 탐색, 빈도수 계산, 중복 확인 등에 자주 활용되므로 숙지할 필요가 있다.
📝 참고: 해시맵(Hash Map) 개념 요약
▶ 키(Key)와 값(Value)의 쌍으로 구성된 자료구조 → Python에서는 dict로 구현됨
** 특징 :
1) 평균 O(1) 시간복잡도로 값 조회/삽입 가능
2) 키는 유일해야 하며, 값은 중복 가능
3) 구현 시 내부적으로 해시 함수를 통해 메모리 주소를 계산
▶ 링크
https://leetcode.com/problems/two-sum/description/