백준 10815 c++ "숫자 카드" -PlusUltraCode-

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

 

[필자 사고]

간단하게 map자료구조를 이용해서 브루트포스를 이용하는게 아닌 logn형태로 탐색을 진행하여 시간복잡도를 맞혔다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

• map<int, int> myMap : 정수를 키(key)로 저장하는 맵. 값은 단순히 존재 여부를 표시하기 위해 1로 둡니다.
• N : 처음에 주어지는 정수의 개수.
• M : 찾고자 하는 수의 개수.

---

 Input() 함수

1. 정수 N을 입력받습니다.
2. N개의 정수를 반복해서 입력받고, 각각을 myMap에 넣습니다.
   • myMap[num] = 1;을 통해, 해당 숫자가 존재한다는 표시를 남깁니다.
   • 맵은 자동으로 키를 정렬하며 저장하기 때문에, 탐색 시 이진 탐색 기반의 O(logN) 시간으로 빠르게 찾을 수 있습니다.

 Game_Start() 함수

1. 정수 M을 입력받습니다.
2. M개의 정수를 차례대로 입력받습니다.
3. 각 정수에 대해 myMap[num]을 확인합니다.
   • 값이 1이라면(즉, 입력 집합에 존재한다면) 1을 출력합니다.
   • 존재하지 않으면 0을 출력합니다.
4. 출력은 공백으로 구분하여 이어 붙여 나갑니다.

---

 main() 함수

1. ios::sync_with_stdio(false);와 cin.tie(0), cout.tie();를 통해 입출력 속도를 빠르게 설정합니다.
2. Input() 함수를 호출해 N개의 숫자를 맵에 저장합니다.
3. Game_Start() 함수를 호출해 M개의 숫자에 대해 존재 여부를 출력합니다.

[소스 코드]

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

map<int, int> myMap;
int N, M;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		myMap[num] = 1;
	}

}

void Game_Start() {
	cin >> M;
	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		if (myMap[num] == 1) {
			cout << 1 << " ";
		}
		else {
			cout << 0 << " ";
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie();
	Input();
	Game_Start();
}