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

알고리즘

 

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

 

---

풀이

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

 

2. card 배열의 원소들을 돌며 숫자가 동일한 카드 번호를 하나로 만들고

    card 배열의 원소들의 개수를 cardCnt배열에 저장한다.

   우선, cardCnt 배열을 완성시키고

     cardCnt 배열의 원소 인덱스를 나타내는 point 변수를 0으로 초기화한다.

     cardCnt에 1을 넣고

     연속되는 동일한 card 번호가 나오는 동안 해당 cardCnt[point]++ 한다.

     반복문을 빠져나오면 해당 card 번호의 개수를 다 세아린 것이므로 point++한다.

   erase와 unique 함수를 통해 동일한 숫자는 한개만 남긴다.

   

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

 

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

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

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

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

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

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

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

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

   

반복문 탈출 시 exist가 0이면 카드가 없는 것이고 exist가 1이면 카드가 있는 것으로 cardCnt[mid]를 통해 확인하고자 하는 숫자에 해당되는 카드의 개수를 알아낼 수 있다.

 

---

성공 코드

#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, point=0;
	vector<int> card, cardCnt;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	for(int i=0; i<n; i++){
		cardCnt.push_back(1);
		while(card[i]==card[i+1]){
			cardCnt[point]++;
			i++;
		}
		point++;
	}
	card.erase(unique(card.begin(), card.end()), card.end());
	cin >> m;
	for(int i=0; i<m; i++){
		exist=0, lt=0, rt=card.size()-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;
			}
		}
		if(exist){
			cout << cardCnt[mid] << " ";
		} else{
			cout << "0 ";
		}
	}

	return 0;
}