[ baekjoon ] #2776 암기왕

문제 링크

💡Idea(Time Exceeded)

1. 수첩 1에 적혀있는 숫자를 저장할 map<int, int>note1을 생성
2. N번 반복하며 값을 입력받아 note1에 insert
3. M번 반복하면서 note2 값을 입력받아 note1에 존재하는지 확인 후 존재하면 1 출력, 존재하지 않으면 0을 출력

   Source Code

   #include <iostream>
   #include <map>
   using namespace std;
   
   int main() {
   	int T;
   	cin >> T;
   	while (T--) {
   		int N, M;
   		map <int, int> note1;
   		cin >> N;
   		for (int i = 0; i < N; i++) {
   			int n;
   			cin >> n;
   			note1.insert(make_pair(n, 1));
   		}
   		cin >> M;
   		for (int i = 0; i < M; i++) {
   			int note2;
   			cin >> note2;
   			if (note1[note2]) {
   				cout << "1" << endl;
   			}
   			else
   				cout << "0" << endl;
   		}
   	}
   	return 0;
   }

   → 위 코드를 제출했더니 시간 초과 발생...

이분 탐색 / 이진 탐색 (Binary Search)

• 정렬된 리스트에서 탐색 범위를 반으로 줄이며 데이터를 탐색하는 방법