백준) 1920번: 수 찾기 in C/C++

Problem

1920번: 수 찾기

 

Solution

 

시간 복잡도가 가장 낮은 알고리즘인 이진 탐색을 이용해서 최대 100,000 크기의 수열에서 최대 100,000 개의 숫자를 탐색해야 한다.

 

더 빠른 코딩을 위해 따로 퀵정렬이나 이진 탐색 알고리즘을 직접 구현하지 않고 C++의 algorithm STL의 sort와 binary_search를 사용했다. (각각 평균 시간복잡도는 nlogn, logn)

 

처음 이 문제를 풀면서 아래 코드와 같이  C++ 의 iostream 라이브러리 내 cin, cout 객체를 사용했었다.

#include <iostream>
#include <algorithm>

int arrN[100000];

using namespace std;

int main(){
	int N, M, i, temp;

	cin >> N;
	for(i=0;i<N;i++){
		cin >> arrN[i];
	}
	
	sort(arrN, arrN + N);
	
	cin >> M;
	for(i=0;i<M;i++){
		cin >> temp;
		cout << binary_search(arrN, arrN + N, temp) << endl;
	}
	
	return 0;
}

그러나 시간 초과가 떠서 실패했다.

질문 게시판에서 문제의 원인을 살펴보니,

cin과 cout 함수는 C언어의 scanf와 printf 함수보다 더 느리다고 한다.

 

더 자세한 내용은 아래 게시글 참고.

https://2heedu.tistory.com/64

입출력 cin과 scanf 속도

https://algospot.com/forum/read/2496/

algospot.com :: 자유게시판: 각 언어별 input method 비교

 

cin, cout 함수를 사용하면서 속도를 빠르게 하기 위해 아래와 같은 코드를 쓸 수도 있다고는 한다.

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

하지만 입출력이 잦고 퍼포먼스가 중요시되는 환경이라면 scanf, printf를 쓰는 게 더 낫다고 한다.

 

또한 endl를 사용하는 경우, flush 수행을 강제하기 때문에 성능 측면에서도 '\n'보다 좋지 않다고 한다.

 

위 내용을 고려하면서 다시 작성을 해보니 시간 초과가 일어나지 않고 빠르게 통과하였다.

단순히 시간복잡도가 낮은 알고리즘을 사용하는 등 내용적 측면 뿐만 아니라 입출력에 대한 성능 등 코드 작성 측면 또한 신경써야 한다는 걸 절감했다.

 

Code

#include <algorithm>
#include <stdio.h>

using namespace std;

int arrN[100000];

int main(){
	int N, M, i, temp;
	
	scanf("%d", &N);
	for(i=0;i<N;i++){
		scanf("%d", &arrN[i]);
	}
	
	sort(arrN, arrN + N);
	
	scanf("%d", &M);
	for(i=0;i<M;i++){
		scanf("%d", &temp);
		printf("%d\n", binary_search(arrN, arrN + N, temp));
	}
	
	return 0;
}