[C++] 숫자 카드 - 백준#10815번

문제

입력 예시

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

출력 예시

1 0 0 1 1 0 0 1

풀이

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

void Func(vector<int>& card, vector<int>& search)
{
	for (int x : search)
	{
		if (find(card.begin(), card.end(), x) == card.end())
			cout << 0 << " ";
		else cout << 1 << " ";
	}
}

int main()
{
	int n, m;
	vector<int> cardNum, searchNum;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		cardNum.push_back(num);
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		searchNum.push_back(num);
	}

	Func(cardNum, searchNum);

	return 0;
}

 

설명

입력 처리를 위해 카드의 갯수를 받을 n과 그에 맞는 값들을 cardNum에, 찾으려는 값들의 갯수를 받을 m과 그 값들을 searchNum 으로 받아주었다.

 

사실 전체적인 로직 자체는 매우 간단하다.

찾으려는 값들 배열인 search에 대해 foreach 문으로 각 요소를 반복하면서, 현재 값이 card 배열에 포함되어 있는 값인지를 find 메서드를 통해서 확인하는 것이다.

 

find 메서드는 <algorithm> 에 포함된 메서드로,

다음과 같은 형태를 취하고 있다.

매개변수로 배열의 시작과 끝, 찾으려는 값을 할당해주고, 반환값에 대해서는 x에 대한 값을 찾을 경우 x를, 값을 찾지 못한 경우 배열의 마지막을 가리키는 반복자를 반환한다.

 

해서 코드의 조건식에서는 x 값을 card 내에서 찾지 못했을 경우, 즉 배열의 마지막을 가리키는 반복자 card.end() 가 반환된 경우 0을 출력하고, 그 외의 경우 x를 찾았다고 판단하여 1를 출력하도록 진행했다.

 

 

사실 문제를 풀어놓고 썩 만족스럽진 못했다.

Func() 내부를 보면 알 수 있듯이 시간 복잡도가 O(n * m) 으로 효율이 좋은 알고리즘이라고는 못하기 때문이다.

해서, 이를 개선할 방법으로 해시 테이블을 사용하여 수정해보았다.

 

#include <unordered_set>

void Func(vector<int>& card, vector<int>& search)
{
	unordered_set<int> cardSet(card.begin(), card.end());

	for (int x : search)
	{
		cout << cardSet.count(x) ? 1 : 0 << ' ';
	}
}

 

가지고 있는 카드 배열 card를 해시 테이블 unordered_set으로 재정의해주고, search 에 대해 반복문을 통해 현재 탐색하는 값 x를 가지고 있는지 확인한다.

unordered_set 의 count() 메서드는 매개변수 x에 대해 보유 여부를 bool 값으로 반환하기에 반환 값에 대해 삼항 연산자를 사용하여 출력값을 달리하는 형태로 코드를 더 간결하게 바꿀 수 있었다.

 

이 경우 평균 시간복잡도는 O(n + m)으로 바뀌어, 처음 코드보다 더 좋은 코드라고 말할 수 있을 것이다.