[백준 10815번/c++] 숫자 카드

알고리즘

 

• 자료 구조
• 정렬
• 이분 탐색

---

풀이

1. 가지고 있는 숫자 카드를 card 배열에 오름차순으로 정렬한다.

 

2. 가지고 있는지 구분하기 위해서

   lt=0, rt=n-1로 카드의 존재 여부를 표시하는 변수 exist=0으로 초기화한다.

 

3. mid=(lt+rt)/2하여

   card[mid] 값이 확인하고자 하는 숫자와 일치하면

      exist 변수를 1로 하고 반복문을 탈출한다.

   card[mid] 값이 확인하고자 하는 숫자보다 작으면

      lt=mid+1로 하여 탐색한다.

   card[mid] 값이 확인하고자 하는 숫자보다 크면

      rt=mid-1로 하여 탐색한다.

   이 과정은 lt<=rt인 동안 반복한다.

   

반복문 탈출 시 exist가 0이면 카드가 없는 것이고 exist가 1이면 카드가 있는 것이 된다.

 

---

함수 이용 시 시간초과

• 함수의 매개변수로 vector 배열을 사용하여 복사하는 과정에서 시간초과 발생한 것 같다.

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

void search(int num, vector<int> card){
	int lt=0, rt=card.size()-1, exist=0, mid;
	while(lt<=rt){
		mid = (lt+rt)/2;
		if(card[mid]==num){
			exist=1;
			break;
		} else if(card[mid]>num){
			rt=mid-1;
		} else{
			lt=mid+1;
		}
	}
	cout << exist << " ";
}

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m, c, num;
	vector<int> card;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> num;
		search(num, card);
	}

	return 0;
}

 

---

성공 코드

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

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m, c, num, lt, rt, mid, exist;
	vector<int> card;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	cin >> m;
	for(int i=0; i<m; i++){
		exist=0, lt=0, rt=n-1;
		cin >> num;
		while(lt<=rt){
			mid = (lt+rt)/2;
			if(card[mid]==num){
				exist=1;
				break;
			} else if(card[mid]>num){
				rt=mid-1;
			} else{
				lt=mid+1;
			}
		}
		cout << exist << " ";
	}

	return 0;
}