백준 10816 숫자 카드 2 [C++] - 탐색, 원소갯수

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

10816번: 숫자 카드 2

소스코드

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

using namespace std;

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

    int T;
    int N, K, num;

    cin >> T;
    vector<int> v;

    for(int i = 0; i < T; i++){
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    
    cin >> T;
    vector<int> answer;
    for(int i = 0; i < T; i++){
        cin >> K;
        auto upper = upper_bound(v.begin(), v.end(), K);
        auto lower = lower_bound(v.begin(), v.end(), K);

        answer.push_back(upper - lower);
    }

    for(auto n : answer){
        cout << n << ' ';
    }
}

- 입력받은 첫번째 벡터를 정렬한다

- upper_bound는 뒤에서, lower_bound는 앞에서 찾기때문에 두개를 빼주면 원소의 개수가 출력가능하다.

 

시간초과 코드 1

int findIndex(vector<int> v, int number){
    auto i= find(v.begin(), v.end(), number);

    if(i != v.end()){
        int index = i - v.begin(); //인덱스가 나온다
        cout << "index : " << index << endl;
        return index;
    }
    else{
        return -1; // 0 번째 인덱스랑 구분하기 위함
    }
}

int main(){
 // ... 
    cin >> m;
    for (i = 0; i < m; i++){
        cnt = 0;
        cin >> number;
        index = findIndex(v1, number);
        if(index == -1){
            v2.push_back(0);
        }
        else{
            do{
                cnt++;
                index++;
            }while(v1[index] == number);
            v2.push_back(cnt);
        }
    }
//...
}

- Index를 찾아서 입력받은 수의 개수를 while문으로 count하는 방법을 생각했다.

- 그러나 N^2의 시간복잡도를 만들어버렸다. 그래서 find 대신 count를 사용해보기로했다.

 

시간초과 코드 2

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, number, i, index, cnt;
    vector<int> v1, v2;

    cin >> n;
    for (i = 0; i < n; i++){
        cin >> number;
        v1.push_back(number);
    }
    sort(v1.begin(), v1.end());

    cin >> m;
    for (i = 0; i < m; i++){
        cin >> number;
        cnt = count(v1.begin(), v1.end(), number);
        v2.push_back(cnt);
    }

    for (i = 0; i < m; i++){
        cout << v2[i] << '\n';
    }
}

또 시간초과. find와 count 모두 시간복잡도가 (N)임에도 역부족인듯하다. 시간초과와 관련된 문제들은 메모리구조, 탐색, 정렬을 공부하기에 좋은듯하다.