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

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

 

제출 코드(시간 초과)

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

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

    int n, m, input;
    set<int> nums;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        nums.insert(input);
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> input;
        cout << binary_search(nums.begin(), nums.end(), input) << '\n';
    }
}

처음에 이렇게 코드를 작성했지만 시간 초과가 떴다

set으로 입력을 받느라 매 번 정렬할 자리를 찾는 게 문제일까 싶어 그 부분을 vector로 바꾸고 마지막에 한 번만 정렬하도록 코드를 작성하였다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, m, input;
    cin >> n;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    sort(nums.begin(), nums.end());
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> input;
        cout << binary_search(nums.begin(), nums.end(), input) << '\n';
    }
}

확실히 시간이 절약되었다

굳이 매 번 정렬할 필요 없는 경우는 set 대신 vector를 사용해야겠다

추가적으로 vector의 다양한 초기화 방법에 대해서도 알아두었다

(참고: https://thinkingtool.tistory.com/entry/C-%EB%B2%A1%ED%84%B0Vector-%EC%B4%88%EA%B8%B0%ED%99%94)

위 코드에서는 n을 먼저 입력받고, n만큼의 길이로 0으로 초기화된 벡터를 생성해서 사용하였다