[백준] 3273번 두 수의 합

문제: 3273번: 두 수의 합

basic-algo-lecture/workbook/0x03.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x03.md at master · encrypted-def/basic-algo-lecture

 

• 강의 코드

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/fc842a288ef843e49e2fe5b6a8bbcf5e
#include <bits/stdc++.h>
using namespace std;

int a[1000001]={};
// 각 자연수의 존재 여부를 저장하는 배열, 아래에서 x-a[i]가 1000000보다 큰 경우를 예외처리하기 싫어서 그냥 배열을 최대 200만으로 잡음
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++) {
    // x-a[i]가 존재하는지 확인
    if(x-a[i] > 0 && occur[x-a[i]]) ans++;
    occur[a[i]] = true;
  }
  cout << ans;
}

/*
공간복잡도 O(2000000), 시간복잡도 O(n)에 풀이가 가능. 만약 입력 형식에서
x가 a 배열보다 먼저 주어졌다면 int a[] 배열은 필요가 없었음.
*/

 

• 내 코드

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; // 수열의 크기
    cin >> n;

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

    int x;
    cin >> x;

    // 0번 인덱스 안 쓸 것
    vector<int> cnts(1000001);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int tmp = x - nums[i];
        if (tmp < 0) continue;
        if (tmp > 1000000) continue;

        if (cnts[tmp] == 1)
            cnt++;

        cnts[nums[i]]++;
    }
    cout << cnt << "\n";


    return 0;
}

 

이번에 강의를 보면서 새롭게 배운 풀이 방식으로 풀어 보았다. 원래 같았으면 O(n^2) 의 시간 복잡도로 풀었을 문제를 O(n) 만에 풀 수 있게 되어서 신기했다.

 

이 문제를 O(n) 시간 안에 풀 수 있는 방법은 현재 주어진 수가 이전에 나왔던 수들 중 어떤 값이랑 더했을 때 x 가 되는지를 알면 되는 것이었다.

 

그럼 이전에 나왔던 수들 중 어떤 값이랑 더해야 X 가 되는지를 O(n) 만에 알 수 있으려면 어떻게 해야할까? 이는 바로 cnts[x - nums[i]] 의 값이 1인지 확인하여 알 수 있다.

 

x 에 nums[i] 값을 뺀 값을 인덱스로 이용해서 cnts 요소 값을 확인하는데 이게 만약 1이면 현재 수랑 이전에 나온 수랑 더해서 x 가 되는 쌍이 존재하는 것이다.

 

새롭게 알게 돼서 너무 기분이 좋다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x03강 - 배열

[실전 알고리즘] 0x03강 - 배열