BOJ 10816 - 숫자 카드 2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

- c++

#include <bits/stdc++.h>
 
#define MAX 10000000
 
using namespace std;
 
int arr[MAX * 2 + 1];
int n, m;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        if (num < 0) arr[MAX + abs(num)]++; 
        else arr[num]++;
    }
    
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int num;
        cin >> num;
        if (num < 0) cout << arr[MAX + abs(num)] << " ";
        else cout << arr[num] << " ";
    }
    
    return 0;
}

 

 

 

배열에 넣어서 처리하는 방식으로 어찌 저찌 통과하긴 했으나

메모리를 상당히 많이 잡아 먹었다.

다른 풀이들을 보니, 이분 탐색으로 많이들 푸는것 같다.

 

- 다른 풀이

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
vector<int> vec;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    sort(vec.begin(), vec.end());
    
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int num;
        cin >> num;
        cout << upper_bound(vec.begin(), vec.end(), num) - lower_bound(vec.begin(), vec.end(), num) << " ";
    }
    
    return 0;
}

 

 

 

 

- 참고

jaimemin.tistory.com/993

백준 10816번 숫자 카드 2

m.blog.naver.com/PostView.nhn?blogId=bestmaker0290&logNo=220820005454&proxyReferer=http:%2F%2F59.16.1.11%2F

알고리즘 기초 - Lower Bound & Upper Bound