백준 10816 - 숫자카드 2

문제요약

상근이가 가지고 있는 숫자카드 N, 숫자를 M개 입력받은 후 입력받은 숫자와 같은 카드를 상근이가 몇개 가지고 있는지 구하는 문제

 

접근

• 입력을 받을 때 마다 0으로 초기화한 배열에 입력받은 수의 배열값에 +1을 한다.
• 음수도 입력받아야 하므로 인덱스는 입력받은 수 + 0으로 만들 수 있는 최대수 (10,000,000)으로 설정한다.
• 그리고 M개의 숫자를 입력받고 그에 해당하는 배열 값을 출력한다.

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;

vector<int> v;

int N, M;
int sum;
int convertNum[20000001] = { 0 };
int negativeToPositive = 10000000;
int main() {
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

	cin >> N;
	int temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		convertNum[temp + negativeToPositive]++;
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> temp;
		cout << convertNum[temp + negativeToPositive]<<" ";
	}
	return 0;
}

실패의 원인

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

위 주석을 풀어주어야 합니다.

ios_base::sync_with_stdio(false)

ios_base::sync_with_stdio(false) 는 c의 stdio와 iostream을 동기화 시켜주는 역할을 하는데 이 떄 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생하여 시간초과가 났습니다.

이 코드를 작성해주어 동기화를 비활성화 시켜줍니다.

c++만의 독립적인 버퍼를 생성시켜 c의 버퍼와 병행하여 사용할 수 없게 하여, 버퍼의 수를 줄이고 실행 속도는 빨라지게 됩니다.

※ 주의

위 코드를 넣었을 때 멀티 쓰레드 환경에서 출력 순서를 보장할 수 없습니다.

또, 버퍼가 분리되었기 때문에 cin과 C의 scanf, gets, getchar등을 같이 사용하면 안되고

cout과 C의 printf, puts, putchar등을 같이 사용하면 예상치 못한 결과를 얻을 수 있습니다.

cin.tie(NULL)

이 코드는 cin과 cout의 묶음을 풀어줍니다.

기본적으로 cin과 cout은 묶여있고 한 스트림이 다른 스트림에서 각 IO작업을 진행하기 저에 자동으로 버퍼를 비워줌을 보장합니다.

이를 사용하면 cin과 cout에 순서를 확실히 보장받을 수 없을 가능성도 있지만 입력을 많이 받아야하는 실패1 과 같은 코드에서는 사용하는 것을 추천합니다.

 

접근2

N과 M을 입력받고 그대로 탐색하면 log N^2이 되므로 시간초과가 날 것 입니다. 따라서 이분탐색으로 접근해보려고 합니다.

• 이분탐색을 위해 N개의 수를 정렬한다.
• 이분탐색을 진행하는데, 카드의 개수를 세야하므로 해당 수가 등장하는 마지막 인덱스 - 첫 인덱스 +1을 해준다.

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N, M;
int lower_bound(int start, int end, int value) {
	int mid = 999;
	while (start <= end) {
		 mid = (start + end) / 2;
		if (v[mid]>=value) {
			end = mid-1;
		}
		else {
			start = mid + 1;
		}
	}

	return start; //해당 숫자카드의 첫 번째 인덱스

}

int upper_bound(int start, int end, int value) {
	int mid = 999;
	while (start <= end) {
		 mid = (start + end) / 2;
		if (v[mid] <= value) {
			start = mid + 1;

		}
		else {
			end = mid-1;
		}
	}
	return end; //해당 숫자카드의 마지막 인덱스
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	int temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		v.push_back(temp);
	}

	sort(v.begin(), v.end());
	cin >> M;
	int num, start , end,low,up;
	for (int i = 0; i < M; i++) {
		cin >> num;
		 start = 0;
		 end = N-1;

		low= lower_bound(start, end, num);
		 up = upper_bound(start, end, num);
		 

		cout << up - low +1 << " ";
	}

	return 0;
}

 

고찰

이분탐색은 시간은 느리지만 메모리는 현저히 적게 사용하였고, 배열을 이용한 값 체크는 20000001이라는 배열크기 때문에 메모리를 상당히 잡아먹었지만 조금 더 빨랐다.

이러한 트레이드 오프를 생각하면서 알고리즘에 접근한다면 더 효율적인 로직에 접근할 수 있을 것 같다.

sync_with_stdio를 복붙해두면서 써서 의미를 제대로 알지 못하고 쓰다가 이번 기회에 확실히 알게된 것 같다. 많은 입력을 받을 땐 입출력에서 시간을 줄이는 방안을 생각해보기도 해야겠다.