백준 10816 - 숫자 카드2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

간단한 이분 탐색 문제였습니다.

문제 조건

출력 예시

이분 탐색을 통해 해당 숫자가 있는지는 찾은 후, 해당 숫자가 존재한다면 똑같은 카드가 몇개인지를 찾는 문제입니다.

존재하는 것은 찾은뒤 -> for문을 통해서 몇개가 있는지 -> 시간초과가 됩니다.

따라서 중복되는 숫자가 몇개가 있는지를 이분 탐색 전에 확인해야합니다.

 

저는 배열 크기를 10,000,000 + 10,000,000 크기의 배열을 선언한 뒤, 양수는 앞의 10,000,000에 저장하고 음수는 뒤에 저장을 했습니다.

이분 탐색의 기본인 탐색 전 정렬은 꼭 해줘야합니다.

 

문제 접근 방법

1. 카드를 입력받으면서 카드의 수를 저장합니다.

2. 카드를 정렬합니다.

3. 이분 탐색을 통해서 카드의 존재 여부를 확인한 뒤, 존재한다면 갯수를 출력합니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int card[500001];
int num[20000001];

bool binary_search(int x) {
	int low = 0;
	int high = N - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (card[mid] == x) return true;
		else if (card[mid] > x) {
			high = mid - 1;
		}
		else low = mid + 1;
	}
	return false;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> card[i];
		if (card[i] >= 0) num[card[i]]++;
		else num[-card[i] + 10000000]++;
	}
	sort(card, card + N);
	cin >> M;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		if (binary_search(x)) {
			if (x >= 0) cout << num[x] << " ";
			else cout << num[-x + 10000000] << " ";
		}
		else {
			cout << "0" << " ";
		}
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!