[ 이진탐색 ] 부품 찾기

난이도 : 중하  풀이시간 : 30분  시간제한 : 1초 

[ 이진탐색 ] 부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

 

:: 입력 조건

 

첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)

넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

 

:: 출력 조건

 

첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

 

---

 

  내   코드  

 

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

using namespace std;

#define endl "\n"

vector<int> n_nums;
vector<int> m_nums;

bool b_search(int start, int end, int target) {
	if (start > end) {
		return false;
	}

	int mid = (start + end) / 2;

	if (target == n_nums[mid]) { return true; }

	else if (target > n_nums[mid]) {
		b_search(mid + 1, end, target);
	}

	else if (target < n_nums[mid]) {
		b_search(start, mid - 1, target);
	}
}

int main() {

	int n=0, m=0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int k = 0;
		cin >> k;
		n_nums.push_back(k);
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		int k = 0;
		cin >> k;
		m_nums.push_back(k);
	}

	sort(n_nums.begin(), n_nums.end());

	for (int i = 0; i < m; i++) {
		if (b_search(0, n, m_nums[i])) {
			printf("yes ");
		}
		else printf("no ");
	}

	return 0;
}

 

  정답  코드  

 

1. 이진탐색을 이용

#include <bits/stdc++.h>

using namespace std;

// 이진 탐색 소스코드 구현(반복문)
int binarySearch(vector<int>& arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) end = mid - 1;
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start = mid + 1; 
    }
    return -1;
}

// N(가게의 부품 개수)와 M(손님이 확인 요청한 부품 개수)
int n, m;
// 가게에 있는 전체 부품 번호들
vector<int> arr;
// 손님이 확인 요청한 부품 번호들
vector<int> targets;

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    
    // 이진 탐색을 수행하기 위해 사전에 정렬 수행
    sort(arr.begin(), arr.end());
    
    cin >> m;
    for (int i = 0; i < m; i++) {
        int target;
        cin >> target;
        targets.push_back(target);
    }
    // 손님이 확인 요청한 부품 번호를 하나씩 확인
    for (int i = 0; i < m; i++) {
        // 해당 부품이 존재하는지 확인
        int result = binarySearch(arr, targets[i], 0, n - 1);
        if (result != -1) {
            cout << "yes" << ' ';
        }
        else {
            cout << "no" << ' ';
        }
    }
}

 

2. 계수정렬을 이용

#include <bits/stdc++.h>

using namespace std;

// N(가게의 부품 개수)와 M(손님이 확인 요청한 부품 개수)
int n, m;
int arr[1000001];
vector<int> targets;

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr[x] = 1;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        int target;
        cin >> target;
        targets.push_back(target);
    }
    // 손님이 확인 요청한 부품 번호를 하나씩 확인
    for (int i = 0; i < m; i++) {
        // 해당 부품이 존재하는지 확인
        if (arr[targets[i]] == 1) {
            cout << "yes" << ' ';
        }
        else {
            cout << "no" << ' ';
        }
    }
}

 

3. 집합(set) 자료형을 이용

#include <bits/stdc++.h>

using namespace std;

// N(가게의 부품 개수)와 M(손님이 확인 요청한 부품 개수)
int n, m;
// 가게게 있는 전체 부품 번호를 담을 집합(set) 컨테이너
set<int> s;
vector<int> targets;

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        int target;
        cin >> target;
        targets.push_back(target);
    }
    // 손님이 확인 요청한 부품 번호를 하나씩 확인
    for (int i = 0; i < m; i++) {
        // 해당 부품이 존재하는지 확인
        if (s.find(targets[i]) != s.end()) {
            cout << "yes" << ' ';
        }
        else {
            cout << "no" << ' ';
        }
    }
}