[C++] 백준 1920번 수 찾기

 

오늘은 목이 아파서 병원에 갔다왔다.

다행히 그냥 조금 헐었다고 해서 약을 처방받았다.

 

비도 내리고... 피곤한 하루지만...

오늘 할 일을 아직 끝내지 못했다.

 

저녁을 먹고 앉았다...

 

... 시작하자

 

문제

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

1920번: 수 찾기

 

 

일단 벡터로 입력을 받고 비교할 것을 pair로 받아야겠다는 생각이 들었다. 그래서 각 수들이 존재하는지 확인하여 second에 1을 저장하면 될 것 같다.

 

 

 

//시간 초과된 코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m,temp;
	cin >> n;
	vector <int> num(n);
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	cin >> m;
	vector <pair<int, int>> result(m);
	for (int i = 0; i < m; i++) {
		cin >> temp;
		result.push_back(make_pair(temp, 0));
		for (int j = 0; j < n; j++) {
			if (num[j] == temp) {
				result[i].second = 1;
			}
			
		}
	}
	for (int i = 0; i < m; i++) {
		cout << result[i].second << "\n";
	}

	return 0;
}

 

음... 뭔가 이중 반복문이 생겨서 시간 초과가 될 것 같았는데... 진짜 발생했다.

아, 알 것 같으면서도 모르겠다...ㅠㅠ

 

 

 

 

 

다른 분들의 풀이를 보니... 아!!!!!!! 맞네... 저번에 풀었던 문제는 잘 생각했으면서...

오늘은 정렬하여 이분 탐색하는 방법이 생각나지 않았다...(힝)

#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
int arr[100010];

void binarySearch(int key){
    int start = 0;
    int end = N-1;
    int mid;

    while(end>=start){
        mid =(start+end)/2;
        if(arr[mid]==key){
            cout<<1<<"\n";
            return;
        }else if(arr[mid]>key){
            end = mid - 1;
        }else{
            start = mid + 1;
        }
    }
    cout<<0<<"\n";
    return;
}


int main(){
    
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N;
    int temp;

    for(int i=0;i<N;i++){
        cin>>temp;
        arr[i]=temp;
    }

    sort(arr,arr+N);

    cin>>M;
    for(int i=0;i<M;i++){
        cin>>temp;
        binarySearch(temp);
    }

    return 0;
}
출처: https://chanqun.tistory.com/14

 

 

 

 

다른 한 분은 binar_search를 사용하였다. 그런데 이 함수는 들어있는지만 판단하고 위치는 파악하지 못한다고 한다. 그래서 값을 찾는 함수는 lower_bound 함수와 upper_bound 함수를 통해 찾을 수 있다고 한다.

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

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, temp;
    vector<int> v;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        cout << binary_search(v.begin(), v.end(), temp) << '\n';
    }
}
출처: https://codejin.tistory.com/108

 

 

 

 

 

 

그럼... 다시 안 보고 작성해볼까...

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

int n, m;
int num[100001];
int temp;

void binarysearch(int x) {
	int start = 0, end = n - 1;
	int mid;
	while (start <= end) {
		mid = (start + end) / 2;
		if (num[mid] == x) {
			cout << "1" << "\n";
			return;
		}
		else if (num[mid] > x) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
	cout << "0" << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	sort(num, num + n);
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		binarysearch(temp);
	}


	return 0;
}

 

 

 

됐다 ㅎㅎ

 

 

하면 할수록 자꾸 머리가 안 돌아가는 것 같다...

계속 하다보면 기억이 나는 날이 오겠지??

 

 

그럼 오늘은 20000~~