[백준] 두 수의 합 3273 (Silver3) — 해시 개념으로 시간복잡도 줄이기

https://www.acmicpc.net/problem/3273

 

문제 간단 요약

• 길이 N의 수열이 주어진다.
• 서로 다른 두 수 a, b를 골라 a + b = X를 만족하는 쌍의 개수를 구하라.
• 같은 쌍을 순서만 바꿔서 세면 안 된다.
  (예: (1, 9)와 (9, 1)은 같은 쌍)

 핵심은 모든 쌍을 다 보지 않고도 조건을 만족하는 경우의 수를 빠르게 세는 것.

 

처음 떠올릴 수 있는 풀이 (하지만 비효율적)

가장 직관적인 방법은 이중 반복문이다.

• 모든 원소 a에 대해
• 나머지 모든 원소 b를 더해보며 a + b == X인지 확인

이 경우 시간복잡도는
-> O(N²)

N이 커질수록 시간 초과가 날 수밖에 없다.

관점 전환: “더하는 대신, 존재 여부를 확인하자”

이 문제를 이렇게 바꿔서 생각할 수 있다.

arr에 어떤 값 a가 있을 때
X - a라는 값이 존재하기만 하면 하나의 쌍이 된다.

 

즉,

• “모든 수를 다 더해보는 문제”가 아니라
• “특정 값이 존재하는지 빠르게 확인하는 문제”

여기서 해시 가 필요해진다.

해시를 이용한 핵심 아이디어

1. 수열의 모든 원소를 해시 테이블에 기록
2. 각 값 i에 대해 X - i가 있는지 확인
3. 쌍은 (i, X-i)와 (X-i, i)가 중복되므로 마지막에 2로 나눈다

사용한 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x;
    cin >> n;

    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    cin >> x;

    vector<int> hash(x + 1);
    int result = 0;

    for(int a : arr){
        if(a >= x) continue;
        hash[a] = 1;
    }

    for(int i = 1; i < x; i++){
        if(hash[i] && hash[x - i]) result++;
    }

    cout << result / 2;
    return 0;
}

---

코드 핵심 설명

• hash[a] = 1
  → 값 a가 배열에 존재함을 표시
• hash[i] && hash[x-i]
  → i + (x-i) = x를 만족하는 두 값이 모두 존재
• / 2
  → (i, x-i)와 (x-i, i)가 중복으로 세어지기 때문

왜 해시가 최적화에 유리한가?

• 모든 쌍을 비교 → O(N²)
• 해시로 존재 여부만 확인 →
  • 해시 테이블 구성: O(N)
  • 탐색: O(X)
  • 전체: O(N + X)

->  시간복잡도가 압도적으로 개선된다.

---

해시(Hash)란 무엇인가?

해시는

해시 함수를 이용해 값을 인덱스로 변환하여
데이터를 빠르게 탐색할 수 있게 해주는 자료구조다.

 

해시의 특징

1. 단방향 접근
   • 키 → 값은 가능
   • 값 → 키는 불가능
2. 빠른 탐색
   • 평균 시간복잡도: O(1)

 코테에서는
“탐색이 많이 발생한다” → 해시를 고려하자

해시 함수에서 중요한 점

• 해시 함수의 결과는
  0 이상, 테이블 크기 미만이어야 한다
• 서로 다른 키가 같은 인덱스로 가는
  충돌을 최소화해야 한다

실제 코딩 테스트에서는
해시 함수를 직접 구현할 필요는 거의 없고
unordered_map, unordered_set을 잘 쓰는 게 핵심이다.

왜 해시가 최적화에 유리한가?

• 모든 쌍을 비교 → O(N²)
• 해시로 존재 여부만 확인 →
  • 해시 테이블 구성: O(N)
  • 탐색: O(X)
  • 전체: O(N + X)

👉 시간복잡도가 압도적으로 개선된다.

 

---

 

이 문제는 투 포인터로도 풀 수 있다고 하니,
다음에는 정렬 + 투 포인터 방식으로도 다시 풀어볼 예정이다.