[알고리즘][정렬] 10815번 숫자 카드 | baekjoon 문제 풀이

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

10815번: 숫자 카드

 

 

숫자 카드를 입력받고

주어진 숫자가 숫자 카드 내에 있는 숫자인지 검사하는 문제.

 

주어진 숫자들의 범위를 보아하니... 최대한 시간을 단축할 수 있도록 문제를 풀어야겠다고 생각했다.

 

 

풀이

첫번째는 시간 초과로 실패하고,

다른 방법으로 다시 도전했을 때 성공했다.

 

우선 성공한 코드부터 설명하자면,

 

 

먼저 숫자 카드를 오름차순으로 정렬하고,

이분검색 (Binary Search)을 재귀 함수로 구현하여 원하는 값을 찾는다.

 

---

 

정렬에는 C++의 algorithm 헤더에 속해있는 sort 함수를 사용했다.

sort 함수는 quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 n log n 이다.

 

quick sort: 분할 정복법. 리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분 리스트를 다시 퀵정렬함

 

 

검색은 이분 검색을 사용했다. 평균 시간복잡도는 logn 이다.

 

이분 검색: 분할 정복법. 오름차순으로 정렬된 배열을 반으로 나누고, x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다.

 

 

<성공한 코드>

#include <iostream>
#include <algorithm>
using namespace std;

int arr[500000];
int x;

int location(int low, int high) {
	int mid;

	if (low > high) return 0;
	else {
		mid = (low + high) / 2;
		if (x == arr[mid]) return mid;
		else if (x < arr[mid]) return location(low, mid - 1);
		else return location(mid + 1, high);
	}
}

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

	int N; cin >> N;

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

	sort(arr, arr + N);

	int M; cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> x;
		if (arr[location(0, N)] == x) cout << 1 << " ";
		else cout << 0 << " ";
	}
}

 

실패했던 코드는 다음과 같다.

 

정렬은 따로 하지 않고

C++의 algorithm 헤더에 있는 find 함수를 사용해주었다.

근데 find 함수를 찾아보니까

아래와 같이 그냥 앞부터 하나하나 비교해가면서 검색을 진행하는 함수였다.

당연히 시간이 오래 걸릴 수밖에...

 

template <class InputIt, class T>
constexpr InputIt find(InputIt first, InputIt last, const T& value) {
  for (; first != last; ++first) {
    if (*first == value) {
      return first;
    }
  }
  return last;
}

 

<시간 초과된 코드>

#include <iostream>
#include <algorithm>
using namespace std;

int arr[500000];

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

	int N; cin >> N;

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

	int answer;

	int M; cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> answer;
		int* p = find(arr, arr + N, answer);
		if (p == arr + N) {
			cout << 0 << " ";
		}
		else {
			cout << 1 << " ";
		}
	}
}