cpp) 백준 10816: 숫자 카드 2

Problem

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

10816번: 숫자 카드 2

상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하시오.

 

 

Solution

- upper_bound와 lower_bound()를 이용한 풀이: 이진탐색, O(logN)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n, tmp;

    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin >> v[i];

    sort(v.begin(), v.end());

    cin >> n;
    vector<int> answer(n);
    for(int i=0;i<n;i++){
        cin >> tmp;
        auto upper = upper_bound(v.begin(), v.end(), tmp);
        auto lower = lower_bound(v.begin(), v.end(), tmp);
        answer[i] = upper - lower;
    }

    for(auto m : answer)
        cout << m << " ";

   return 0;
}

 

cpp의 upper_bound와 lower_bound를 이용하면 쉽게 풀 수 있다. upper_bound()는 이진탐색으로 해당 숫자가 끝나는 위치를 반환하고 lower_bound()는 이진탐색으로 해당 숫자가 시작되는 위치를 반환한다.

 

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

 

위 코드는 C와 C++의 표준 stream의 동기화를 끊는 역할을 한다. cin과 cout의 속도가 C의 입출력 속도에 비해 떨어지기 때문에 저 코드를 사용해 속도를 높일 수 있다. 하지만 동기화를 끊게되면 C의 입출력 함수(scanf, printf, getchar...)를 더 이상 사용하지 못 한다. 위 코드를 쓸 때, c의 입출력 함수를 쓰지 않도록 조심하자.

 

 

- HashMap을 이용한 풀이: O(1)

 

#include<iostream>
#include<unordered_map>

#pragma warning(disable: 4996) // scanf 사용시 보안 경고 무시

using namespace std;

unordered_map<int, int> cards;
int n, m, tmp;

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

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> tmp;
        cards[tmp]++;
    }

    cin >> m;
    for(int i=0;i<m;i++){
        cin >> tmp;
        cout << cards[tmp] << ' ';
    }

   return 0;
}

 

 

Reference

https://hwan-shell.tistory.com/300

백준 10816] C++ 숫자 카드 2

https://puffinknight.tistory.com/69

#pragma warning(disable : 4996)

https://ip99202.github.io/posts/sync_with_stdio(false)-%EC%93%B8-%EB%95%8C-%EC%A3%BC%EC%9D%98%ED%95%A0-%EC%82%AC%ED%95%AD/ 

sync_with_stdio(false) 쓸 때 주의할 사항

https://bbeomgeun.tistory.com/18

[baekjoon 10816] 숫자 카드2 - Hashmap, 이분탐색 (C++)

https://dev-su.tistory.com/60

C++ 자료구조 - unordered map(hash map)