[C++] 백준 2776번 암기왕

 

 

눈이다~~ 펑펑(은 아니지만) 눈이 옵니다~

하늘에서 눈이 옵니다~

 

 

오전 볼일을 끝내고 좀 쉬다가 노트북 앞에 앉았다.

무슨 문제를 풀지 고민하다가 암기왕이 되고 싶어 암기왕 문제를 풀려고 한다.

 

 

문제

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

2776번: 암기왕

 

음... 어?? 그런데 문제를 잘 읽어보니 예전에 푼 문제랑 비슷한 것 같다.

이 문제는 테스트케이스의 개수를 입력받기 때문에 while을 통해 테스트케이스의 개수만큼 반복해주면 되겠다. while 문 안에서는 수첩1에 적어 놓은 정수들을 배열에 입력받고 정렬한다. 여기서 정렬을 하는 이유는 수첩2에 적어 놓은 정수를 입력받을 때마다 이진 탐색을 해주기 위해서이다. 그래서 해당 숫자가 있으면 1을 아니면 0을 출력하도록 해준다.

 

 

 

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

int A[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T,n,m,temp;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> A[i];
		}
		sort(A, A + n);
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> temp;
			if (binary_search(A, A + n, temp)) {
				cout << "1" << "\n";
			}
			else {
				cout << "0" << "\n";
			}
		}

	}
	
	return 0;
}

 

 

ㅎㅎ 맞았다~~~

예전에는 버벅거리던 문제를 이렇게 한번에 푸니까 기분이 좋다 ㅎㅎ

 

 

 

 

 

 

 

다른 분의 풀이를 살펴보니 map과 unordered_map, 이분탐색 이렇게 총 3가지 방법으로 푸신 분이 있었다.

시간 복잡도는 map이 O(log(n)), unordered_map은 O(1), 이분 탐색은 O(log2(n))이다. 조 단위를 넘어가지 않는 이상 이분 탐색의 속도가 unordered_map보다 더 빠르다고 한다.

 

그래서 이 분이 푼 방법 중 unordered_map을 보았다. 수첩1에 적혀있는 정수를 입력받아 map의 key로 사용해 해당 key의 value에 1을 넣어주었다. 그리고 수첩2에 적혀있는 정수를 입력받아 map에 해당 key가 존재하는지 확인하는 방법을 사용하였다.

//백준 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;
}
출처: https://se-jung-h.tistory.com/entry/BOJC-%EB%B0%B1%EC%A4%80-2776-%EC%95%94%EA%B8%B0%EC%99%95

 

 

 

 

 

set으로 푼 분도 있었다. set도 비슷하게 사용하는 것 같다.

#include <iostream>
#include <set>

using namespace std;

int main() {

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

	int t,n,m,num;



	cin >> t;

	while (t--) {
	set<int> s;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> num;
			s.insert(num);
		}

		cin >> m;

		for (int i = 0; i < m; i++) {
			cin >> num;
			if (s.find(num) != s.end()) //숫자를 찾았다면
				cout << 1 <<"\n";
			else
				cout << 0 << "\n";
		}
	}
}
출처: https://flowersayo.tistory.com/102

 

 

 

그런데 이렇게 보니까 이분탐색을 직접 구현하여 알고리즘을 작성해보기도 해야겠다는 생각이 들었다. (계속 안 하다보면 까먹을지도 모르니까...ㅎㅎ)

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

int A[1000001];
int T, n, m, temp;
void binar(int t) {
	int start = 0;
	int end = n;
	int mid;

	while (start <= end) {
		mid = (start + end) / 2;
		if (t > A[mid]) {
			start = mid + 1;
		}
		else if (t < A[mid]) {
			end = mid - 1;
		}
		else if (t == A[mid]) {
			cout << "1" << "\n";
			return;
		}
	}
	cout << "0" << "\n";
	return;
}


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

	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> A[i];
		}
		sort(A, A + n);
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> temp;
			if (binary_search(A, A + n, temp)) {
				cout << "1" << "\n";
			}
			else {
				cout << "0" << "\n";
			}
		}

	}
	
	return 0;
}

됐다 ㅎㅎ