[C++]백준 알고리즘 15719번

풀이는 아래와 같다.

#include <iostream>
 
using namespace std;
 
int main(){
    int n,m;
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    
    cin >> n;
    
    bool* counter = new bool[n];
 
    int j;
    
    for(int i=0; i<n; i++){
        cin >> j;
        if (counter[j]){
            m = j;
            break;
        }else{
            counter[j] = true;
        }
    }
    
    cout << m;
}

시행착오:

처음에 이 문제를 풀었을 때 앞선 1269번처럼 <map>을 include해서 하려고 했었는데 결과적으로 보면 그렇게 했어도 똑같았을 거 같긴 하다. 여기서 문제가 되었던 점은 우선 입력이 문제에서 최대 천만개까지 들어가야 되기 때문에 int형 배열을 선언할때 로컬 변수로 하면 최대 범위를 훨씬 넘어서는 것 같다는 점이다. 이렇게 한 방법은 틀렸다고 떴다. 그래서 선택한 방법은 c++ 의 new 동적할당이었는데, 이마저도 너무 큰 메모리를 차지해서 그런지 시간초과가 나는 것 같았다. (확실하지 x) 그리고 위의 동적할당으로 int형 포인터를 선언하구 알고리즘은 모든 입력값들을 더한 sum에서 1부터 n-1까지 더한 n*(n-1)/2를 빼는 것으로 했었는데, 아마 sum이 너무 커서 계산이 복잡해서 그런지 시간초과가 났다... 암튼 그래서 결국은 counter를 bool형 포인터로 바꾼 결과 훨씬 메모리를 적게 차지하게 되지 않았을까 생각이 든다. 흐음 그리고 처음에는 scanf,printf를 썼었는데 아래의 세줄을 추가해서 cin, cout을 그냥 써봤다. 지금 다시 scanf, printf로 해서 제출해봤는데 되려나..? 엇 시간초과가 났다.

 

 ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

 

흐음 이게 더 빠르다니 아직 C에 대해서 나는 연구할게 많은 것 같다.... 암튼 이 문제는 알고리즘보다는 큰 숫자를 처리하는 법에 대한 지식이 조금이나마 느는데 도움이 되었다. 나중에 공부하고 보면 더 문제가 제대로 와닿을 듯하다.