[백준] 15719번 중복된 숫자

문제

1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.

둘째 줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1보다 크거나 같고, N-1보다 작거나 같은 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.

출력

M을 출력하라.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int num;
  cin >> num;
  int arr[num];
  fill_n(arr, num, 0);
  for (int i = 0 ; i< num;i++) {
      int key;
      cin >> key;
      arr[key]++;
  }  

  for(int i = 0; i< num;i++) {
     if (1 < arr[i]) {
        cout << i << "\n";
        return 0;
     }
  }
}

매우 간단해 보이는 문제이지만 위 두개를 입력해주지 않으면 시간 초과가 발생한다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, s;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i=0;i<n;i++){
        int a; cin >> a;
        s += a;
    }
    cout << s-n*(n-1)/2;
}

가우스 덧셈 : n * (n-1)/2 => 1-n까지의 합공식 

오랜만에 보는데 다시 익혔다. 그걸 전체 합으로 빼니 답이 나온다.

배열을 쓰는 방법보다 빠를 것 같다.