[정글 알고리즘] - [중] - 백준 2295-해시 테이블 - 세 수의 합

처음엔 3중 for문으로 접근했지만 문법 오류만 5개가 쏟아졌고, 고치고 나니 이번엔 시간 초과. 핵심은 a + b + c = d를 a + b = d − c로 바꿔 두 수 합을 set에 미리 저장하는 것이었다.

📋 문제 소개

항목	내용
문제 번호	백준 2295
난이도	골드 4
분류	해시 테이블, 정렬
핵심 자료구조	set() (해시 테이블 기반 O(1) 조회)
시간 제한	2초
N 범위	5 ≤ N ≤ 1,000 (원소는 최대 200,000,000)
입력	첫째 줄: N / 다음 N줄: 집합 U의 원소 (한 줄에 하나씩)
출력	세 수의 합으로 만들 수 있는 가장 큰 d 출력

입력 예시	출력 예시
5 2 3 5 10 18	18

중요한 조건: 문제에서 "x, y, z, k가 서로 같아도 된다"고 명시되어 있다. 즉, 같은 인덱스의 수를 여러 번 사용해도 된다. (단, 집합이므로 같은 값의 원소는 입력에 없음)

🐛 처음 작성한 코드 (오류 5개)

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input))       # 오류 1: input 뒤에 () 없음

def serch(start, end):
    global result
    if end >= 0:                 # 오류 2: 조건이 반대 (항상 바로 return)
        return
    else:
        for j in range(end-1, start, -1):    # 오류 3: range 끝이 start → 0번 인덱스 제외
            for l in range(end-2, start, -1):
                for k in range(end-3, start, -1):
                    result = j + l + k       # 오류 4: 인덱스 합 (값이 아님)
                    if arr(end) == result:   # 오류 2-b: arr() → arr[]
                        return result

                    return result            # 오류 5: if 밖 return → 첫 조합만 보고 종료

serch(0, n-1)
print(f"{result}")

#	오류 코드	수정 코드	원인 설명
1	int(input)	int(input())	input은 함수 객체 자체. input()이어야 실제로 호출해서 값을 읽음
2	if end >= 0: return	if end < 0: return	end=n-1은 항상 ≥0이므로 호출 즉시 종료. 함수 본문 한 줄도 실행 안 됨
3	arr(end)	arr[end]	리스트 원소 접근은 []. ()는 함수 호출 문법
4	result = j + l + k	result = arr[j]+arr[l]+arr[k]	j, l, k는 인덱스 번호. 실제 값은 arr[j]로 꺼내야 함
5	if 블록 밖에 return result	if 조건 만족 시만 return	첫 번째 k 조합을 보자마자 무조건 return → 전체 탐색 불가

🔍 오류 1·3 상세 — 괄호 종류의 의미

문법	의미	예시
함수()	함수를 실제로 호출해서 반환값을 가져옴	input() → 키보드에서 한 줄 읽어서 문자열 반환
함수	함수 객체 자체를 가리킴 (실행 안 됨)	input → "<built-in function input>" 이라는 객체
리스트[i]	리스트의 i번째 원소를 읽음	arr[2] → arr의 3번째 값
리스트(i)	리스트를 함수처럼 호출 → TypeError 발생	arr(2) → TypeError: 'list' object is not callable

기억 포인트: 파이썬에서 ()는 "실행해줘", []는 "꺼내줘"다.

🔍 오류 2 상세 — 종료 조건이 반대

함수 첫 줄이 if end >= 0: return이면 어떻게 되는지 추적해보자.

호출	end 값	if end >= 0 결과	실행 결과
serch(0, 4)	4	True	❌ 즉시 return → for문 한 번도 안 돌아감
serch(0, -1)	-1	False	for문 실행 (하지만 이 경우는 탐색할 게 없음)

재귀 종료 조건의 원래 의도는 "더 이상 탐색할 게 없을 때(end가 음수가 됐을 때) 멈춰라"였다. 그래서 올바른 조건은:

if end < 0:      # end가 음수 = 탐색 범위 없음 → 종료
    return

🔍 오류 4 상세 — 인덱스와 값 구분

배열	인덱스 j=1	인덱스 l=2	인덱스 k=3	j+l+k (오류)	arr[j]+arr[l]+arr[k] (정답)
[2, 3, 5, 10, 18]	1	2	3	1+2+3 = 6 ← 인덱스 합	3+5+10 = 18 ← 값의 합

기억 포인트: for문의 변수(j, l, k)는 위치 번호. 그 위치의 값이 필요하면 반드시 arr[j]처럼 꺼내야 한다.

🔍 오류 5 상세 — return 위치가 잘못된 경우

❌ 잘못된 위치	✅ 올바른 위치
for k in range(...): result = arr[j]+arr[l]+arr[k] if arr[end] == result: return result return result # ← 여기! # if가 False여도 여기 도달하면 return # 즉 k 첫 번째 값 하나만 보고 끝	for k in range(...): if arr[j]+arr[l]+arr[k] == arr[end]: return arr[end] # return이 if 안에만 있음 # 조건 불만족 시 다음 k로 계속 진행

핵심: return은 함수를 즉시 종료한다. 반복문 안에 return이 있으면 첫 번째 반복에서 무조건 함수가 끝난다. 조건을 만족할 때만 return하려면 반드시 if 블록 안에 있어야 한다.

⏱️ 오류 수정 후에도 시간 초과가 나는 이유

오류를 모두 잡으면 아래 코드가 된다. 하지만 이 코드는 여전히 시간 초과다.

arr.sort()

def serch(start, end):
    for j in range(end-1, start-1, -1):
        for l in range(j-1, start-1, -1):
            for k in range(l-1, start-1, -1):
                if arr[j] + arr[l] + arr[k] == arr[end]:
                    return arr[end]
    return None

for end in range(n-1, -1, -1):
    result = serch(0, end)
    if result is not None:
        print(result)
        break

N	3중 for문 최악 경우	+ 바깥 end 루프	총 연산	판정
100	≈ 161,700	× 100	≈ 16,170,000	⚠️ 경계
1,000	≈ 166,167,000	× 1,000	≈ 166,167,000,000	❌ 시간 초과

결론: N=1,000이면 거의 4중 for에 가까운 O(N⁴) 수준. Python은 초당 약 1~2천만 연산이므로 2초 제한으로는 턱없이 부족하다.

💡 핵심 아이디어 — 식 변형으로 O(N²) 달성

발상 전환: 세 수를 동시에 찾지 말고, 두 수 합을 미리 저장한다.

원래 관점	바뀐 관점
a + b + c = d 세 수를 동시에 탐색 → O(N³)	a + b = d − c 두 수 합 저장 후 조회 → O(N²)

단계	작업	복잡도
1	모든 arr[i] + arr[j] 값을 sum_set에 저장	O(N²)
2	d 후보를 큰 것부터 순서대로 고름 (정렬 후 역순)	O(N)
3	각 d에 대해 c를 순회하며 d − c가 sum_set에 있는지 확인	O(N²) × O(1) = O(N²)
전체	O(N²) + O(N²) = O(N²)	✅ N=1,000 → 약 100만

🗂️ 왜 set(해시 테이블)인가 — in 연산 속도

자료구조	x in 컨테이너 속도	N=1,000,000 조회 시간	내부 원리
리스트 []	O(N)	≈ 1,000,000번 비교	처음부터 끝까지 하나씩 탐색
set {}	O(1)	≈ 1번 계산	해시값으로 위치를 바로 계산해서 확인

# set 기본 사용법
sum_set = set()

sum_set.add(5)       # 값 추가
sum_set.add(8)
sum_set.add(13)

print(8 in sum_set)   # True  → O(1)
print(9 in sum_set)   # False → O(1)

해시 테이블 원리: 값을 저장할 때 해시 함수로 위치를 결정한다. 조회할 때도 같은 함수로 위치를 계산해서 바로 확인하므로 크기에 무관하게 O(1)이다.

🧩 최적화 코드 한 줄씩 이해하기

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))       # (1) 한 줄에 하나씩 입력

arr.sort()                         # (2) 오름차순 정렬 (큰 값을 나중에 탐색)

sum_set = set()
for i in range(n):
    for j in range(n):             # (3) 중복 인덱스 허용 (문제 조건: x,y,z,k 같아도 됨)
        sum_set.add(arr[i] + arr[j])  # (4) 두 수의 합 전부 저장

for d in range(n-1, -1, -1):      # (5) 가장 큰 수부터 d 후보 탐색
    for c in range(d, -1, -1):    # (6) c는 d 이하 (c <= d)
        if arr[d] - arr[c] in sum_set:  # (7) d-c가 두 수 합으로 만들어지는지
            print(arr[d])
            exit()                 # (8) 찾는 즉시 출력 후 종료 (최댓값이므로)

라인	설명	주의점
(2)	arr.sort()	큰 수부터 역순으로 확인해야 "처음 찾은 것 = 최댓값" 보장
(3)	range(n) 둘 다	문제 조건 "x,y,z,k 서로 같아도 됨" → 같은 인덱스 두 번 써도 됨
(7)	arr[d] - arr[c] in sum_set	핵심 조건. 이게 True면 a+b = d-c 성립 → a+b+c = d 성립
(8)	exit()	break는 for 하나만 탈출. exit()은 프로그램 전체 종료 → 중첩 루프 탈출에 유용

🔬 단계별 시뮬레이션 — 입력 {2, 3, 5, 10, 18}

Step 1 — 정렬

arr = [2, 3, 5, 10, 18]    (인덱스: 0, 1, 2, 3, 4)

Step 2 — sum_set 구성 (두 수 합 전부 저장)

i	arr[i]	arr[i] + arr[j] (j = 0~4)
0	2	4, 5, 7, 12, 20
1	3	5, 6, 8, 13, 21
2	5	7, 8, 10, 15, 23
3	10	12, 13, 15, 20, 28
4	18	20, 21, 23, 28, 36

sum_set = {4, 5, 6, 7, 8, 10, 12, 13, 15, 20, 21, 23, 28, 36}

Step 3 — d, c 순회로 정답 탐색

d	arr[d]	c	arr[c]	d - c = arr[d] - arr[c]	in sum_set?	결과
4	18	4	18	18 − 18 = 0	❌ (0 없음)	다음 c
4	18	3	10	18 − 10 = 8	✅ (3+5=8 존재)	print(18) → exit()

확인: 8 = arr[1] + arr[2] = 3 + 5 이므로 a=3, b=5, c=10, d=18 → 3 + 5 + 10 = 18 ✅

📊 Before / After 전체 비교

항목	❌ 처음 코드	✅ 최종 코드
입력	int(input) → 함수 객체 변환 시도	int(input()) → 정상
종료 조건	if end >= 0 → 즉시 종료	없음 (while/for 구조로 대체)
리스트 접근	arr(end) → TypeError	arr[d] → 정상
연산 대상	j+l+k → 인덱스 합	arr[i]+arr[j] → 값의 합
알고리즘	3중 for → O(N³) 이상	set 활용 → O(N²)
결과	실행 즉시 오류 / 시간 초과	N=1,000 → ✅ 통과

⏱️ 시간 복잡도 정리

단계	코드	복잡도	N=1,000
정렬	arr.sort()	O(N log N)	≈ 10,000
sum_set 구성	for i, for j: sum_set.add()	O(N²)	1,000,000
d, c 탐색	for d, for c: if _ in sum_set	O(N²)	1,000,000
전체	O(N²) 지배	O(N²)	✅ 통과

✅ 최종 코드

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))    # 한 줄에 하나씩 입력

arr.sort()                      # 정렬 (큰 수부터 확인해야 최댓값 보장)

# 두 수의 합 가능한 값 전부 저장 (해시 테이블)
sum_set = set()
for i in range(n):
    for j in range(n):          # 중복 인덱스 허용 (문제 조건)
        sum_set.add(arr[i] + arr[j])

# 가장 큰 d부터 검사
for d in range(n - 1, -1, -1):
    for c in range(d, -1, -1):
        # a + b + c = d  →  a + b = d - c
        if arr[d] - arr[c] in sum_set:
            print(arr[d])
            exit()              # 처음 찾은 것이 최댓값 → 즉시 종료

💬 마무리

문법 오류 5개를 잡고 나서도 3중 for문은 N=1,000에서 시간 초과가 났다. 핵심은 a+b+c=d를 a+b=d−c로 바꾸는 식 변형이었다. 두 수 합을 set에 저장하면 O(N²)+O(1) 조회로 O(N²)에 해결된다.

초보 때 가장 자주 틀리는 건 알고리즘보다 괄호 한 개, 조건 방향 하나 같은 문법이다. 오류 메시지를 천천히 읽는 습관이 먼저다.