B10816

개요

백준 문제 10816번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/10816

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다.
상근이는 숫자 카드 N개를 가지고 있다.
정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

코드

#include <algorithm>
#include <iostream>
using namespace std;
const int arrMax = 500000;
const int numMax = 10000001;
int marking[arrMax];
int sortedMark[arrMax];
int num[arrMax];
int plusNum[numMax];
int minusNum[numMax]; // think as just * -1
//1. 숫자 입력받음 
//

void binSearch(int N,int obj)
{
	int i=0,j,mid;
	j = N;
	while(i <= j)
	{
		mid = (i + j)/2;
		if(num[mid] == obj)
		{
			if(obj < 0)
			{
				cout << minusNum[obj * -1];
			}
			else
			{
				cout << plusNum[obj];
			}
			return;		
		}
		else if(num[mid] > obj)
		{
			j = mid -1;
		}
		else if(num[mid] < obj)
		{
			i = mid + 1;
		}

	}
	cout << 0;
}


void solve()
{
	int N,M;
	cin >> N;
	fill_n(plusNum,numMax,0);
	fill_n(minusNum,numMax,0);
	for(int i=0;i<N;i++)
	{
		cin >> num[i];
		if(num[i] < 0)
		{
			minusNum[num[i] * -1] += 1;
		}
		else
		{
			plusNum[num[i]] += 1;
		}
	}
	cin >> M;
	for(int i=0;i<M;i++)
	{
		cin >> marking[i];
		sortedMark[i] = marking[i];
	}
	
	sort(num,num+N);
	for(int i=0;i<M;i++)
	{
		if(i != 0)
		{
			cout << " ";
		}
		binSearch(N,marking[i]);
		
	}

	/*
	for(int i=0;i<M;i++)
	{
		if(marking[i] < 0)
		{
			cout << minusNum[-1 * marking[i]];
		}
		else
		{
			cout << plusNum[marking[i]];
		}
		if(i != M-1)
		{
			cout << " ";
		}
	}		
	*/
	

}

int main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();

}

풀이

1. 10815번과 마찬가지로 입력에 대한 정렬
2. 1 이번에는 입력시에 빈도수를 계산해야한다.
3. 정렬 한 것에 대한 이분 탐색
4. 탐색 결과에 대한 출력(빈도수)

피드백, 메모

문제를 잘못이해했음
문제 읽는데 더 시간을 들이자.