[백준/C++] 1920번 수 찾기

---

갑자기 동아리원 한 명이 이 문제 ios::sync_with_stdio(0) 하나 차이로 통과하고 못한다고 이야기해서 진짜인가? 하고 풀어봤다. 정답 비율을 보니 그럴 수 있겠다는 생각이 들었다.

문제를 보며 가장 먼저 한 생각은 그냥 10만개 솔트 N log(N) 2번이면 오바되고 하나의 배열을 솔트하고 이분탐색하는 방법이 시간 내에 통과할 수 있겠구나 했지만 귀찮아서 map으로 되나 짜봤다.

---

/**
 * @file 1920
 * @author fpqpsxh
 * @date 2023-01-10
 */
#include <bits/stdc++.h>
using namespace std ;

int main()
{
    int N, M, tmp ;
    map<int, bool> mp ;
    vector<int> ans ;
    cin >> N ;
    while(N--)
    {
        cin >> tmp ;
        mp[tmp] = true ;
    }

    cin >> M ;
    while(M--)
    {
        cin >> tmp ;
        ans.push_back(mp[tmp]) ;
    }
    
    for(int i : ans)
        cout << i << '\n';
}

---

여기서 정말 흥미로운 점은 정답을 모두 모아놓고 한 번에 출력하는 것은 시간 내에 통과가 되지만

한 번 결과를 계산하고 출력하고를 반복하게되면 시간 초과를 받는다.

 

출력하기 위해 IO 시스템에 출입하거나 출력 준비를 하거나 인터럽트 하는데 생각보다 많은 시간이 걸리는게 아닌가 생각해봤다. (차량도 섰다 갔다하는 도심 주행이 연비가 안좋지 않은가?ㅎㅎ)

---

느낀점: OS 책 다시보면서 원인을 찾아봐야겠다.

문제: https://www.acmicpc.net/problem/1920

1920번: 수 찾기