[백준] 1920번. 수 찾기

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

#include <iostream>
using namespace std;

int main()
{
	int N; 
	cin >> N;
	int* a = new int[N];
	for (int i = 0; i < N; i++)
		cin >> a[i];

	int M;
	cin >> M;
	int* b = new int[M];
	for (int i = 0; i < M; i++)
		cin >> b[i];

	// b의 원소 하나랑 'a의 원소 전체' 비교하기
	int j;
	for (int i = 0; i < M; i++) {
		for (j = 0; j < N; j++) {
			// 배열 a에 있는 원소일 경우, 1 출력
			if (b[i] == a[j]) {
				printf("1\n");
				break; // 내부 루프 탈출
			}
		}
		
		// 배열 a의 끝까지 검사했지만 없는 원소일 경우, 0 출력
		if (j == N) printf("0\n");
		//else // j가 N이 되기 전에 이미 원소를 발견한 경우, b의 다음 원소로 넘어간다.
		//	continue; 
	}

	delete[] a, b;

	return 0;
}

배열 a의 인덱스 0부터 N-1까지 선형 탐색을 하니까 시간 초과 문제가 발생한다.. 배열 a를 퀵소트로 정렬한 다음에 이진 탐색을 적용하자! 이렇게 하면, 시간복잡도가 O(N)에서 O(logN)으로 단축된다!

1. scanf로 입력 받기

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm> // std::sort
using namespace std;

void binarySearch(int* arr, int n, int key) {
	int left = 0, right = n - 1;
	int mid;

	while (left <= right) {
		mid = (left + right) / 2;

		if (arr[mid] == key) {
			printf("1\n");
			return;
		}
		else if (arr[mid] > key) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	// left > right인 경우, key를 발견하지 못했으므로 0 출력
	printf("0\n");
	return;
}

int main() {
	int n;
	scanf("%d", &n);

	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	// 이진 탐색을 위해 배열 정렬하기
	sort(arr, arr + n);

	int m; 
	scanf("%d", &m);

	int tmp;
	for (int i = 0; i < m; i++) {
		scanf("%d", &tmp);

		// 배열 a에 tmp가 있는지 이진탐색으로 확인하기
		binarySearch(arr, n, tmp);
	}

	return 0;
}

📌 cin 대신에 scanf를 써야 시간 초과가 안 된다.
그리고 scanf 함수의 경우, 백준에서는 통과 되지만 비주얼 스튜디오에서는 다음과 같은 빌드 오류가 발생한다.

Severity Code Description Project File Line Suppression State
Error C4996 'scanf': This function or variable may be unsafe.
Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

예전에는 매번 #define _CRT_SECURE_NO_WARNINGS 이 코드를 작성했었는데, 찾아보니 더 편한 방법이 있었다!
https://blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=lidaxi043682&logNo=221734325035
아래 사진처럼 SDL check를 No로 설정하면, scanf Error가 Warning으로 바뀌면서 프로그램을 실행할 수 있게 된다.

그래도 cin을 쓰고 싶다면? 아래 코드를 통해 실행 시간을 단축시킨다.

ios_base::sync_with_stdio(0);
cin.tie(0);

2. cin으로 입력 받기

int main() {
	// cin, cout 시간초과 문제 해결
	ios_base::sync_with_stdio(0); // stdio와의 동기화 해제
	cin.tie(0); // cout과의 바인딩 해제

	int n;
	cin >> n;

	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	// 이진 탐색을 위해 배열 정렬하기
	sort(arr, arr + n);

	int m; 
	cin >> m;

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

		// 배열 a에 tmp가 있는지 이진탐색으로 확인하기
		binarySearch(arr, n, tmp);
	}

	return 0;
}

📌 추가로 공부할 것
cin으로 공백이 포함된 숫자 여러 개를 입력 받을 때, 숫자 하나 입력 받고 곧바로 binarySearch 함수를 호출하는 줄 알았는데 아니었다...!! cin에서 m개의 숫자를 다 입력 받고 나서, 다시 m번 반복하며 binarySearch 함수를 호출한다. 아마 스트림 버퍼라는 곳에 임시적으로 입력값을 저장해두는 거 같은데, cin이 구체적으로 어떻게 입력을 받는 건지 다시 공부할 필요가 있다!
참고: https://modoocode.com/213