3SUM·4SUM 풀이 고르는 법, n 한계 계산과 중복·쌍 개수 버그 점검

3SUM 을 제출했더니 예제는 맞는데 시간 초과가 나거나, 같은 조합이 여러 번 나오거나, 쌍 개수를 세는 문제에서 답이 조금씩 모자란 적 있으시죠? 결론부터 말하면 정렬 뒤 투 포인터 변형은 "몇 개를 고르고 무엇을 돌려주는지"와 n 으로 정하고, 버그는 거의 다 같은 값이 여러 번 나올 때 생겨요. 3개는 하나를 고정하고 투 포인터, 4개는 n 이 1,000 근처면 쌍 합 해시로 바꾸고, 개수를 셀 때는 같은 값 묶음을 곱해서 더해요.

이 글은 원리 증명보다 고르는 기준과 직접 잰 숫자를 다뤄요. 시간·메모리는 Apple M1, 파이썬 3.15.2 로 쟀고(2026-11-05), 문제 제약은 CSES 문제 페이지에서 확인했어요. 절대 시간은 기기마다 다르니 방식 사이의 배수로 읽어 주세요. 구간(부분 배열) 문제에서 투 포인터·슬라이딩 윈도우·누적합을 고르는 기준은 투 포인터 언제 쓰나, 음수·0 입력 판단표에 따로 정리해 두었고, 여기서는 정렬한 배열에서 원소 몇 개를 골라 합을 맞추는 문제만 봐요.

정렬 뒤 투 포인터 변형 판단표, 무엇을 돌려주나부터

정렬하고 양 끝에서 좁혀 오는 틀은 같아도, 돌려줄 값이 바뀌면 포인터를 움직인 뒤 하는 일이 달라져요. 문제를 읽으면 먼저 "고를 원소 수"와 "돌려줄 것"을 적어요.

표의 "합 < k 쌍 개수" 줄이 투 포인터가 해시보다 확실히 나은 자리예요. 해시는 "정확히 같은 값"만 찾을 수 있어서 부등식 개수에는 못 써요. 반대로 "합 = x 쌍이 있나"만 묻는다면 정렬이 필요 없는 해시가 보통 더 빨라요.

3SUM 중복 제거 방식별 비용, 건너뛰기 vs 집합

"합이 0 인 서로 다른 세 값 조합을 중복 없이" 같은 문제에서 중복을 없애는 방법은 크게 셋이에요.

• 건너뛰기: 고정값 a[i] 가 바로 앞과 같으면 그 i 를 통째로 건너뛰고, 답을 찾은 뒤에는 같은 a[lo] 를 건너뛰어요.
• 집합: 건너뛰지 않고 찾은 조합을 전부 set 에 넣어 겹치는 것을 지워요.
• 고정 + 해시: 하나를 고정하고 나머지에서 "필요한 값이 이미 나왔나"를 집합으로 찾아요. 정렬은 중복 정리용으로만 써요.

세 방법 모두 같은 조합 목록을 냈어요. 시간은 크게 갈렸어요.

값이 넓게 퍼져 중복이 거의 없으면 건너뛰기와 집합은 비슷해요. 차이는 같은 값이 많을 때 나요. 값 범위 ±50 에 원소 3,000개면 같은 값이 평균 30개씩이에요. 건너뛰기는 서로 다른 고정값 101개에 대해서만 안쪽 투 포인터를 돌리지만, 집합 방식은 3,000번을 다 돌고 같은 조합을 수없이 만든 뒤 지워요. 그래서 약 35배 느렸어요.

운영 데이터는 대개 중복이 많아요. 금액·수량·점수처럼 단위가 정해진 값은 범위가 좁고, 같은 값이 수십~수천 번 나와요.

건너뛰는 위치는 두 곳이고 순서가 중요해요.

def three_sum_zero(nums):
    a = sorted(nums)
    out = []
    for i in range(len(a) - 2):
        if i > 0 and a[i] == a[i - 1]:
            continue                      # ① 같은 고정값은 한 번만
        if a[i] > 0:
            break                         # 정렬돼 있으니 뒤도 전부 양수
        lo, hi = i + 1, len(a) - 1
        while lo < hi:
            s = a[i] + a[lo] + a[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append((a[i], a[lo], a[hi]))
                lo += 1
                hi -= 1
                while lo < hi and a[lo] == a[lo - 1]:
                    lo += 1               # ② 답을 찾은 "뒤에만" 건너뛰기
    return out

print(three_sum_zero([-1, 0, 1, 2, -1, -4]))   # [(-1, -1, 2), (-1, 0, 1)]
print(three_sum_zero([0, 0, 0, 0]))            # [(0, 0, 0)]

①을 a[i] == a[i + 1] 로 쓰면 첫 번째 −1 을 건너뛰고 두 번째 −1 을 고정해서 (-1, -1, 2) 를 놓쳐요. ②를 답을 찾기 전에 하면 마찬가지로 두 번째 자리에 같은 값을 쓰는 조합을 놓쳐요. a[i] > 0 에서 멈추는 줄은 목표가 0 일 때만 맞아요. 목표가 다른 값이면 a[i] * 3 > target 처럼 바꿔야 해요.

n 한계 직접 계산, 3SUM·4SUM 은 파이썬으로 어디까지 되나

같은 O(n²) 이라도 언어에 따라 통과하는 n 이 달라요. 답이 없는 최악의 입력(1~10억 무작위, 목표 1)으로 "세 수 합이 있나"를 쟀어요.

CSES 1641 Sum of Three Values 는 n ≤ 5,000, 시간 제한 1초예요. C++ 로는 안쪽 단계가 약 1,250만 번이라 넉넉하지만, 위 측정대로 순수 파이썬은 약 3.9초라 통과하기 어려워요. 이때 고를 수 있는 길은 둘이에요.

1. 같은 알고리즘을 C++·자바·Go 로 옮겨요. 가장 확실해요.
2. 가지치기를 넣어요. 정렬돼 있으니 a[i] + a[i+1] + a[i+2] > x 면 바깥 루프를 끝내고, a[i] + a[n-2] + a[n-1] < x 면 그 i 를 건너뛰어요. 최악 입력에서는 효과가 없으니 보험으로만 봐요.

4SUM 은 차이가 더 커요. CSES 1642 Sum of Four Values 는 n ≤ 1,000, 시간 제한 1초, 메모리 512MB 예요.

둘을 고정하는 O(n³) 은 n=1,000 에서 안쪽 단계가 약 1.7억 번(n³/6)이에요. 단계가 단순해 C++ 로는 1초 안에 들 수 있지만 파이썬으로는 안 돼요. 쌍 합 해시는 "앞쪽 쌍의 합"을 딕셔너리에 쌓으면서 "뒤쪽 쌍"으로 조회해요.

def four_sum_positions(a, x):
    d = {}                                  # 쌍의 합 -> (i, j), 모두 j 보다 앞 위치
    for j in range(len(a)):
        for k in range(j + 1, len(a)):      # 뒤쪽 쌍 (j, k) 로 조회
            p = d.get(x - a[j] - a[k])
            if p:
                return p + (j, k)
        for i in range(j):                  # (i, j) 를 앞쪽 쌍으로 등록
            d[a[i] + a[j]] = (i, j)
    return None

j 를 기준으로 "조회 먼저, 등록 나중"이라 저장된 쌍은 늘 j 보다 앞 위치만 써요. 그래서 네 위치가 겹치지 않아요. 무작위 작은 배열 2,000개로 전수 조합과 대조해 모두 맞았어요. 대가는 메모리예요. 쌍이 n(n−1)/2 = 499,500 개라 파이썬에서 약 66MiB 를 썼어요. 같은 방식을 n=1만에 쓰면 쌍이 약 5,000만 개라 파이썬 딕셔너리로는 수 GB 가 들어요. 쌍 합 해시는 n 이 1,000~수천인 4SUM 전용으로 생각해 두면 돼요.

쌍 개수 세기, 같은 값에서 덜 세는 버그

"합이 정확히 x 인 쌍이 몇 개인가"에서 가장 흔한 실수는 찾기 문제의 코드를 그대로 가져와 cnt += 1; lo += 1; hi -= 1 로 쓰는 거예요. 값이 모두 다르면 맞지만, 같은 값이 있으면 덜 세요.

고치는 법은 경우 두 개로 나눠요. a[lo] 와 a[hi] 값이 다르면 양쪽 묶음 크기를 세어 곱하고 두 묶음을 한꺼번에 넘겨요. 값이 같으면 lo~hi 사이가 전부 그 값이니 남은 개수 m 에서 m(m−1)/2 를 더하고 끝내요.

def count_pairs_equal(a, x):
    a = sorted(a)
    lo, hi, cnt = 0, len(a) - 1, 0
    while lo < hi:
        s = a[lo] + a[hi]
        if s < x:
            lo += 1
        elif s > x:
            hi -= 1
        elif a[lo] == a[hi]:
            m = hi - lo + 1
            cnt += m * (m - 1) // 2
            break
        else:
            l2, h2 = lo, hi
            while a[l2] == a[lo]:
                l2 += 1
            while a[h2] == a[hi]:
                h2 -= 1
            cnt += (l2 - lo) * (hi - h2)
            lo, hi = l2, h2
    return cnt

print(count_pairs_equal([1, 1, 3, 3], 4), count_pairs_equal([2, 2, 2], 4))   # 4 3

0~5 범위 값으로 길이 2~10 인 무작위 배열 5,000개를 전수 탐색과 대조했더니, 한 칸씩 좁히는 코드는 1,765개(35%)에서 틀렸고 위 코드는 모두 맞았어요. collections.Counter 로 "지금까지 본 값의 개수"를 세며 한 번 훑는 방법도 모두 맞았어요. n=20만, 값 1~1,000 에서 투 포인터 81ms, Counter 107ms 로 비슷했어요. 정렬이 이미 돼 있지 않으면 Counter 쪽이 코드가 짧고 실수할 곳이 적어요(파이썬 collections 문서).

합이 k 미만인 쌍 개수, 투 포인터 vs 이분 탐색

부등식 개수는 해시로 못 세요. 정렬 뒤 고를 수 있는 방법은 투 포인터와 원소마다 이분 탐색이에요. n=20만, 값 1~10억, k=10억으로 쟀어요.

• 투 포인터: 149ms (조건을 만족하면 cnt += hi - lo)
• 원소마다 bisect_left(a, k - x, i + 1): 406ms
• 둘 다 정렬 103ms 포함, 결과는 같은 10,019,050,186

파이썬 bisect 문서 대로 bisect_left 는 lo 인자를 받아서, i + 1 을 넘기면 자기 자신과 앞쪽 원소를 빼고 셀 수 있어요. 이분 탐색은 원소마다 독립이라 "각 원소와 짝이 되는 개수"까지 필요할 때 편하고, 전체 개수 하나만 필요하면 투 포인터가 약 2.7배 빨랐어요. 경계(bisect_left 냐 bisect_right 냐, 미만이냐 이하냐)를 헷갈리기 쉬우니 이분 탐색 판단표와 경계 버그 체크리스트 도 같이 보면 좋아요.

결과 10,019,050,186 은 32비트 정수 최대 2,147,483,647 의 약 4.7배예요. n=20만이면 쌍이 최대 약 200억 개라, C++·자바에서 개수를 int 로 두면 조용히 틀린 값이 나와요. 개수 변수는 처음부터 long long·long·int64 로 둬요.

가장 가까운 합 문제에서 놓치는 것

"합이 x 에 가장 가까운 세 수"처럼 정확히 맞지 않아도 되는 문제는 매 단계 차이를 비교하며 최선을 갱신해요. 틀은 3SUM 과 같지만 확인할 곳이 셋 있어요.

• 동점 규칙: x−1 과 x+1 이 똑같이 가까우면 무엇을 내야 하는지 문제에 적혀 있는지 봐요. abs(s - x) < abs(best - x) 로 갱신하면 먼저 찾은 쪽이 남고, "작은 쪽" 규칙이 있으면 (abs(s - x), s) 튜플로 비교해요.
• 초깃값과 오버플로: 초깃값을 INT_MAX 같은 큰 수로 두면 best - x 계산이 넘칠 수 있어요. 첫 후보 a[0] + a[1] + a[2] 로 시작하거나 차이를 64비트로 계산해요.
• 일찍 끝내기: 차이가 0 이면 더 볼 필요가 없으니 바로 돌려줘요. 정확히 맞는 답이 많은 입력에서 시간이 크게 줄어요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

정렬 뒤 투 포인터 변형의 버그는 예외 없이 조용히 틀린 값을 내요. 아래 순서로 보면 대부분 잡혀요.

1. 돌려줄 것 다시 읽기. "있나"와 "몇 개"와 "목록"은 맞았을 때 하는 일이 달라요. 찾기 코드를 개수 문제에 복사하지 않았는지 봐요.
2. 같은 값 처리. 개수 문제는 묶음 곱하기와 m(m−1)/2, 목록 문제는 건너뛰는 두 위치(①은 앞과 비교, ②는 답 뒤에서만)를 확인해요.
3. 같은 위치 재사용. 2개를 고르면 lo < hi, 3개면 안쪽이 i + 1 부터, 4개 쌍 합 해시면 "조회 먼저, 등록 나중"인지 봐요.
4. 정수 폭. 합은 원소 최대 × 고를 수, 개수는 n(n−1)/2 까지 가요. 원소 10⁹ 를 네 개 더하면 4×10⁹ 라 32비트를 넘어요.
5. n 과 언어. 파이썬이면 3SUM 은 n 2,000 안팎, 4SUM O(n³) 은 n 200~300 안팎이 1~3초 선이에요. 그보다 크면 알고리즘이나 언어를 바꿔요.
6. 중복이 많은 입력으로 시간 재기. 값 범위가 넓은 무작위 입력과, 전부 같은 값·좁은 범위 입력을 둘 다 넣어요. 집합 중복 제거는 뒤쪽에서만 느려져요.

고친 뒤엔 값 범위를 0~5 처럼 좁힌 무작위 작은 배열로 전수 탐색과 대조해요.

import random
from itertools import combinations

def brute_pairs(a, x):
    return sum(p + q == x for p, q in combinations(a, 2))

for _ in range(5000):
    a = [random.randint(0, 5) for _ in range(random.randint(2, 10))]
    x = random.randint(0, 10)
    assert count_pairs_equal(a, x) == brute_pairs(a, x), (a, x)

도입 전에 따질 것

서비스 코드에 이런 변형을 직접 넣기 전에 확인해요.

• 정렬 비용과 출처: 이미 정렬된 목록(DB ORDER BY, 정렬된 가격표)이면 투 포인터가 가장 싸요. 새로 정렬해야 하면 n=20만 파이썬에서 정렬만 약 0.1초가 들고, 정확히 같은 값만 찾는 문제라면 해시가 더 단순해요. 정렬 비용은 파이썬·자바 정렬 성능 판단표 에서 key 함수별로 볼 수 있어요.
• 원래 위치가 필요한가: 위치를 출력하거나 저장해야 하면 (값, 위치) 쌍으로 정렬해야 하고, 메모리와 시간이 늘어요.
• 조합 수의 상한: 3SUM 목록은 최악에 결과가 O(n²) 개일 수 있어요. 결과를 전부 메모리에 담을지, 하나씩 내보낼지 먼저 정해요.
• 4개 이상: 고를 수가 4개를 넘으면 쌍 합 해시도 메모리가 빠르게 늘어요. 이때는 문제를 "합이 x 이하인 부분집합"처럼 다른 꼴로 바꿀 수 있는지, 값 범위가 작아 DP 가 되는지부터 봐요.

자주 묻는 질문

3SUM 중복 제거는 set 에 넣으면 안 되나요?

결과는 맞아요. 다만 같은 값이 많은 입력에서 크게 느려져요. n=3,000, 값 범위 ±50 에서 건너뛰기 36ms, 집합 1,259ms 였고 전부 0 이면 1.2ms 대 1,321ms 였어요. 고정값과 두 번째 값을 건너뛰는 방식으로 쓰는 게 안전해요.

파이썬으로 n=5,000 인 3SUM 이 시간 초과가 나요.

순수 파이썬 O(n²) 은 답이 없는 최악 입력에서 n=5,000 에 약 3.9초였어요(Apple M1). 1초 제한이면 C++·자바로 옮기는 게 가장 확실해요. 가지치기는 최악 입력에서 효과가 없어서 보험 정도예요.

4SUM 은 O(n³) 투 포인터로 충분한가요?

n 이 수백이면 충분해요. n=1,000 이면 안쪽 단계가 약 1.7억 번이라 파이썬으로 약 87초(추산)였어요. 이때는 쌍 합을 딕셔너리에 저장하는 O(n²) 방식으로 바꿔요. n=1,000 에서 0.48초, 메모리 약 66MiB 였어요.

합이 x 인 쌍 개수가 조금씩 모자라요.

맞는 쌍을 찾은 뒤 양쪽을 한 칸씩만 좁히고 있을 가능성이 커요. 같은 값 묶음 크기를 곱해서 더하고, 양 끝이 같은 값이면 남은 개수 m 으로 m(m−1)/2 를 더한 뒤 끝내야 해요. 정렬이 필요 없다면 Counter 로 한 번 훑는 방법이 더 단순해요.

쌍 개수 결과가 음수로 나와요.

32비트 정수 오버플로예요. n=20만이면 쌍 개수가 최대 약 200억이라 int 최대값(약 21억)을 넘어요. 개수 변수를 64비트로 바꾸고, 원소 여러 개를 더하는 합도 64비트로 계산해요.

합이 k 미만인 쌍은 이분 탐색과 투 포인터 중 무엇이 낫나요?

전체 개수 하나만 필요하면 투 포인터가 빨랐어요(n=20만에서 149ms 대 406ms, 정렬 포함). 원소마다 짝이 되는 개수가 따로 필요하거나, 질의마다 k 가 바뀌어 정렬 배열을 여러 번 쓰는 경우엔 이분 탐색이 편해요.

정리

• 정렬 뒤 투 포인터 변형은 "고를 수"와 "돌려줄 것"으로 골라요. 부등식 개수는 투 포인터, 정확히 같은 값 찾기는 해시가 보통 단순해요.
• 3SUM 중복 제거는 건너뛰기로 해요. 같은 값이 많을수록 집합 방식과의 차이가 커졌어요(최대 약 1,000배).
• 파이썬 한계는 3SUM n 2,000 안팎, 4SUM O(n³) n 200~300 안팎이에요. 4SUM n=1,000 은 쌍 합 해시로 0.48초·약 66MiB 였어요.
• 개수 문제는 같은 값 묶음을 곱하고, 개수와 합은 64비트로 담고, 좁은 값 범위의 무작위 대조로 검증해요.
• 구간 합·슬라이딩 윈도우 쪽 판단은 투 포인터 언제 쓰나, 음수·0 입력 판단표 에서 이어서 볼 수 있어요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 투 포인터 원리 — 정렬 2SUM 증명과 슬라이딩 윈도우 단조성에서 도식과 코드로 단계별로 풀었어요.