[백준/3273번/C++] 두 수의 합

• 문제

 

• 풀이

입력받은 값을 배열에 쭉 저장한 뒤, 두 값이 합쳐졌을 때 x가 되는 경우를 판단해야 하는 문제이다.

 

뭔가 답이 알듯말듯해서 혼자 고민하다가 다른 분의 풀이(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x03/solutions/3273.cpp) 를 참고했다. 이미 너무 깔끔한 코드인데 개인적으로 조건문 내부에서 사칙연산을 그대로 넣는 걸 좋아하지 않아서 value 변수로 따로 빼주었다.

 

#include <iostream>
using namespace std;

int a[1000001] = {};
bool occur[2000001];
int n, x;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;

    for (int i = 0; i < n; i++) {
        int value = x - a[i];
        if (value > 0 && occur[value]) ans++;
        occur[a[i]] = true;
    }
    cout << ans;
}

 

풀이 코드에선 occur 배열을 사용해 이미 등장한 숫자를 기록하고, 이를 통해 각 숫자와 x를 만들 수 있는 수의 존재 여부를 빠르게 확인할 수 있다. 작동 원리는 다음과 같다.

 

1. 먼저 각 원소 a[i]에 대해 x - a[i]를 계산하여 occur[x - a[i]]의 값을 확인해 해당하는 값이 존재하는지 확인한다.

2. 만약 occur[x - a[i]]가 true이면, 이는 이전에 등장한 수 중 x - a[i]가 존재함을 의미한다. 따라서 a[i]와 x - a[i]의 합이 x가 되는 쌍이 존재하므로, ans를 1 증가시킨다.

3. 이후 occur[a[i]] = true;로 a[i]가 등장했음을 기록해준다.

 

중복 검사는 occur 배열을 통해 O(1) 시간에 이루어지고, 숫자의 등장 횟수를 따로 기록하였기 때문에 occur[x - a[i]]만 확인하므로 전체 시간 복잡도는 O(n)가 된다.

아이디어가 좋은 풀이라 다음에 비슷한 문제가 또 있으면 이걸 참고해서 혼자 풀어봐야겠다.