백준 10816번 c++ 풀이

안녕하세요 오늘은 이분탐색으로 풀면 빨리 풀리는 문제를 풀어보겠습니다. (다른 방식으로 푼 저는 엄청난 메모리와 시간을 맛봤지요 맞긴했지만..)

두가지 방법으로 문제를 풀어보겠습니다만, 2번째 방법을 추천드립니다.

 

전략1

1. 범위를 확인한 후, 20000001길이의 벡터를 선언해준다(어레이로 선언하면 배열 길이 제한때문에 안된다)

2. x+= 10000000을 해준후, x+1번째 배열의 원소 값에 1을 더해준다.

3. 2번째 입력때 x+= 10000000을 해준다음 그 위치에 있는 원소값을 출력한다.

 

코드1(내가 한 번에 풀었던 방식):

#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main(){
	vector<int> arr(20000001);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin>>N;
	for(int i= 0; i<N; i++){
		int x;
		cin>>x;
		x+=10000000;
		arr[x] += 1;
	}
	int M;
	cin>>M;
	for(int i= 0; i<M; i++){
		int x; 
		cin>>x;
		x+=10000000;
		cout<<arr[x]<<" ";
	}
}

 

전략2: 

1. N을 입력받은 후에 길이가 N인 v라는 벡터를 선언하고 입력을 받고 sort함수를 통해 정렬을 해준다.

2. M값을 입력받고 그 값이 길이인 answer라는 벡터를 선언해주고 값을 받고 그 값을 upper_bound을 통해 뒤에서 부터 그 값을 찾은 위치를 upper라는 변수로 두고, 똑같이 앞에서부터 탐색하여 lower라는 값에 선언해준다.

3. upper-lower를 통해 그 값의 개수를 출력해준다.

코드2(문제에서 주어진 알고리즘 분류인 이분탐색으로 풀이한 코드):

#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++)
        cin>>v[i];
    sort(v.begin(), v.end());
    cin >> M;
    for (int i = 0; i < M; i++) {
        int K;
        cin >> K;
        auto upper = upper_bound(v.begin(), v.end(), K);
        auto lower = lower_bound(v.begin(), v.end(), K);
       	int answer = upper - lower;
		cout<<answer<<" ";
    }
}