2021.02.18 알고리즘

📌 백준 10816 문제

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

📌 시간초과

처음코드

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

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    int num;
    int chk = 0;
    
    cin >> n;
    vector<int> v1;
    
    for(int i = 0; i<n; i++)
    {
        cin >> num;
        v1.push_back(num);
    }
    
    cin >> m;
    
    for(int i = 0; i<m; i++)
    {
        cin >> num;
        
        for(int i = 0; i<v1.size(); i++)
        {
            if(num == v1[i])
                chk++;
        }
        cout << chk << ' ';
        chk = 0;
    }
    cout << '\n';
    return 0;
}

이렇게 제출을 하게되면 두 번째 for문에서 linear search로 nxm 만큼의 시간이 걸리기 때문에 시간초과에 걸리게 된다. 따라서 이진 탐색으로 이를 바꿔서 해결해야한다.

📌 c++의 upper_bound와 lower_bound

c++ stl에서는 upper_bound와 lower_bound를 제공한다.

lower_bound

용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

사용법(배열)

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

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5
    
	return 0;
}

사용법(벡터)

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

int main() {

	vector<int> arr = { 1,2,3,4,5,6,6,6 };
	cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

    // 결과 -> lower_bound(6) : 5
    
	return 0;
}

upper_bound

용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

사용법(배열도 위와 동일)

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

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();

    // 결과 -> upper_bound(3) : 3
	return 0;
}

출처 : https://chanhuiseok.github.io/posts/algo-55/

📌수정 코드

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

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    int num;
    
    cin >> n;
    
    vector<int> v1;
    
    for(int i = 0; i<n; i++)
    {
        cin >> num;
        v1.push_back(num);
    }
    sort(v1.begin(), v1.end());
    
    cin >> m;
    for(int i = 0; i<m; i++)
    {
        cin >> num;
        cout << (upper_bound(v1.begin(), v1.end(), num) - v1.begin()) - (lower_bound(v1.begin(), v1.end(), num) - v1.begin()) << ' ';
    }
    cout << '\n';
    return 0;
}

Stl에 있는 upper_bound, lower_bound는 이진탐색을 가지고 구현되어 있는데 이진 탐색의 코드는 아래와 같다.

int mylower_bound(int * arr, int n, int key){
    int start = 0;
    int end = n;
 
    int mid = n;
    while(end - start >0){  //start 가 end 와 같지 않고, 넘지 않을 때
        mid = (start+end)/2;    //중앙 index
 
        if(arr[mid] < key){ //key 값이 중앙 값보다 크면
            start = mid + 1;//mid 보다 오른쪽으로
        }else{  //key 값이 중앙값보다 작거나 같으면
            end = mid;  //mid 포함 왼쪽 (포함하는 이유는 key값과 같은게 없을 때 큰수중 가장 작은값을 위해)
        }
 
    }
    return end+ 1;
}


int myupper_bound(int *arr, int n, int key){
    int start = 0;
    int end = n;
    int mid;
 
    while(end - start > 0){
        mid = (start+end)/2;
 
        if(arr[mid] <= key){    //lower_bound와 다른 점은 여기 '=' 하나
            start = mid + 1;
        }else{
            end = mid;
        }
 
    }
 
    return end +1;
}


출처: https://blockdmask.tistory.com/168 [개발자 지망생]