[Algorithm] BAEKJOON 15719번: 중복된 숫자 (C++)

 

https://www.acmicpc.net/problem/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을 출력하라.

 

 

 

 

풀이

처음의 접근법은 입력받은 모든 숫자를 배열에 저장하고 개수가 2개인 수를 찾으려고 한 것이었지만 문제의 N 조건이 매우 커서 메모리 초과가 났다.

좀 더 생각해보니 그냥 입력받은 모든 수열의 원소를 더한 수에서 1부터 N-1 까지 수의 합을 빼면 M을 구할 수 있다는 걸 깨달았다.

 

 

C++ 소스 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, t, A = 0, s = 0;
    
    cin >> N;
    
    // N개의 숫자를 입력받아 A에 합산
    for (int i = 0; i < N; i++) {
        cin >> t;
        A += t;
    }
    
    // 1부터 N-1까지의 합을 계산하여 s에 저장
    for (int i = 1; i < N; i++) {
        s += i;
    }
    
    // A에서 s를 빼서 결과 출력
    cout << A - s;
    
    return 0;
}