[코드업] 기억력 테스트 2 (C++)

기억력 테스트 2

 

문제

이 문제는 주현이가 기억력 테스트를 통해 숫자의 존재 여부를 확인하는 프로그램을 작성하는 문제이다.

주어진 숫자들 중에서 각 질문에 대해 해당 숫자가 존재하는지 여부를 출력한다.

입력으로는 먼저 숫자의 개수 N과 그 다음 줄에 N개의 숫자가 주어지고 그 후에 질문의 수 M과 M개의 질문이 주어진다.

M개의 질문에 대해 숫자가 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

풀이

 

n의 범위가 (1 <= N <= 10,000,000) 이기 때문에 O(n^2)으로 문제를 풀이한다면 시간초과가 난다.

 

그래서 <int, bool>map을 이용하여 기억할 각 숫자를 true로 저장하고 해당 숫자가 map에서 true인지 찾는 방법으로 풀이했다. 

// 맵을 이용한 풀이
#include <iostream>
#include<map>
// https://codeup.kr/problem.php?id=1430&rid=0
using namespace std;

int main() {
	int n,m, num;

	cin >> n;

	map <int, bool> memorys ; // 맵 선언

	for (int i = 0; i < n; i++) { // 해당 숫자를 키로 true 저장
		cin >> num;
		memorys[num] = true;
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> num;

		if (memorys[num]) { // 해당 숫자가 true 일 때 1 출력
			cout << "1 ";
		}
		else { // false 일 때 0 출력
			cout << "0 ";
		}
	}

	return 0;
}

 

 

하지만 이 방법보다 더 효율적인 방법에 대해 고민하다가 HashSet을 이용하면 더 효율적으로 풀이할 수 있을거 같다고 생각해 HashSet으로 풀이했다.

// 해시 셋을 이용한 풀이
#include <iostream>
#include <unordered_set>
// https://codeup.kr/problem.php?id=1430&rid=0
using namespace std;

int main() {
	int n, m, num;
	cin >> n;

	unordered_set<int> memorys; // 맵 대신 해시셋을 사용하여 빠른 검색 가능

	for (int i = 0; i < n; i++) {
		cin >> num;
		memorys.insert(num); // set에 숫자 추가
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> num;

		if (memorys.find(num) != memorys.end()) { // 숫자가 발견되면 1 출력
			cout << "1 ";
		}
		else { // 발견되지 않으면 0 출력
			cout << "0 ";
		}
	}

	return 0;
}

HashSet (위), Map(아래)

 

HashSet으로 풀이한 풀이가 Map으로 풀이한 풀이보다 시간과 메모리가 더 효율적인 것을 확인할 수 있었다.

 

HashSet의 시간복잡도는 평균 O(1) 이지만 최악의 경우(해시 충돌)에는 O(n) 이기 때문에 잘 생각하고 사용해야겠다.

 

※ 해시 충돌 : 해시테이블에 데이터를 저장할 때, 서로 다른 데이터가 동일한 해시값을 가지는 상황

 

CodingTestPractice/CodeUp/1차원 배열/기억력 테스트 2.cpp at main · seungdo1234/CodingTestPractice