BOJ(C++) / 백준 2776 : 암기왕

백준 2776 : 암기왕

https://www.acmicpc.net/problem/2776

2776번: 암기왕

 

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

 

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

 

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

 

코드

map 사용

//백준 2776 암기왕
#include <iostream>
#include <map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, N, M;
	cin >> T;
	for (int k = 0; k < T; k++) {
		cin >> N;
		map<int, int> m; //해쉬 맵
		for (int i = 0; i < N; i++) {
			int num;
			cin >> num;
			m[num] = 1;
		}
		cin >> M;
		for (int j = 0; j < M; j++) {
			int num;
			cin >> num;
			if (m[num] == 1) //존재할 때
				cout << "1\n";
			else //존재하지 않을 때
				cout << "0\n";
		}
	}
	return 0;
}

 

unordered_map 사용

//백준 2776 암기왕
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, N, M;
	cin >> T;
	for (int k = 0; k < T; k++) {
		cin >> N;
		unordered_map<int, int> um; //해쉬맵
		for (int i = 0; i < N; i++) {
			int num;
			cin >> num;
			um[num] = 1;
		}
		cin >> M;
		for (int j = 0; j < M; j++) {
			int num;
			cin >> num;
			if (um[num] == 1) //존재할 때
				cout << "1\n";
			else //존재하지 않을 때
				cout << "0\n";
		}
	}
	return 0;
}

2021.06.26 - [알고리즘/개념정리] - 알고리즘 / unordered_map

알고리즘 / unordered_map

 

이분 탐색 사용(binary_search)

//백준 2776 암기왕
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, N, M;
	cin >> T;
	for (int k = 0; k < T; k++) {
		cin >> N;
		vector<int> s;
		for (int i = 0; i < N; i++) {
			int num;
			cin >> num;
			s.push_back(num);
		}
		sort(s.begin(), s.end());
		cin >> M;
		for (int j = 0; j < M; j++) {
			int num;
			cin >> num;
			if (binary_search(s.begin(), s.end(), num))
				cout << "1\n";
			else
				cout << "0\n";
		}
	}
	return 0;
}

2021.08.29 - [알고리즘/개념정리] - 알고리즘(C++) / 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound()

알고리즘(C++) / 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound()

 

설명

map, unordered_map, 이분탐색 세 가지 방법으로 풀어보았다. 

세 가지 방법 모두 맞는 방법이다. 하지만 걸리는 시간 차이가 조금 있다. 

map은 1928ms, unordered_map은 1240ms, 이분 탐색은 568ms이 걸렸다.

속도 : map < unordered_map < 이분탐색

시간 복잡도 map : O(log(n)), unordered_map : O(1), 이분 탐색 : O(log2(n))

처음에는 O(1)의 시간이 가장 빠른 줄 알고 풀었지만 조 단위가 넘어가지 않는 이상 이분 탐색의 속도가 더 빠르다는 것을 알 수 있었다. 

다음에서 더 자세히 확인할 수 있다.

https://www.acmicpc.net/board/view/57406

글 읽기 - HashMap이 이분탐색보다 느린 이유가 뭔가요?

 

고찰

걸린 시간 : 10분

T를 생각하지 않아서 틀렸었지만 바로 어떤 부분이 틀렸는지 확인하고 고칠 수 있었다.

 

난이도

Silver 4