[c++]백준1920번: 수 찾기

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

1920번: 수 찾기

---

가장먼저 떠오른 방법

:

 "이 안에 X라는 정수가 존재하는지 알아내라" 라는 키워드에서

algorithm 라이브러리의 (find(A.begin(), A.end(), num) 함수가 떠올랐다.

 

find() 함수는 첫 번째 인자로 벡터의 시작점,

두 번째 인자로 벡터의 종점,

세 번째 인자로 '찾고자 하는 정수'(여기서는 num)를 넣어준다.

반환은 num을 찾았으면 해당 원소의 반복자를 반환하고,

찾지 못했으면 해당 범위의 마지막 end()반복자를 반환한다.

(반복자란 ? : https://eehoeskrap.tistory.com/263 참고)

 

따라서 find함수를 이용하여 1 과 0 을 출력면 된다고 생각했는데...

시간초과가 떴다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(0); cin.tie(0);     // 시간초과방지

    int n;
    scanf("%d", &n);
    vector<int> A(n);

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

    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int num;
        scanf("%d", &num);
        if (find(A.begin(), A.end(), num) != A.end())		// 찾았다면 1 출력
            printf("1\n");
        else
            printf("0\n");
    }

    return 0;
}

 

---

다르게 접근해본 방법

:

cin 과 cout 때문에 시간초과가 났나,

cout 에서 endl -> \n로 바꾸지 않아 시간초과가 났나,

이 두 방법을 건드렸는데도 해결되지 않아 접근법을 다시 고민해보았다.

 

하지만 도저히 어떻게 접근해야하는지 아이디어가 떠오르지 않아 구글링 한 결과,

이진탐색으로 푸는 문제였다.

 

이진 탐색 은 배열의 중간(mid)을 기준으로 데이터를 탐색하기 때문에 

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 이므로

일단 이진탐색을 수행하기에 앞서 오름차순 정렬을 해주었다.

 

작년 하반기 알고리즘 전공 수업에서 배운 이진 탐색 기억을 떠올리면서,

구글링 한 결과 이진탐색의 개념을 간단하게 설명하자면

"변수 3개( start, end, mid ) 를 사용하여 검색범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘" 이다.

 

이진 탐색을 사용하면 시간복잡도(O(logN))가 상대적으로 빠르기 때문에

내가 기존에 짰던 'find 함수를 이용하여 벡터의 처음부터 끝까지 전수조사하는 O(N) 방법'보다  

더 빠르게 원하는 원소를 검색할 수 있다.

 

이 방법이라면 시간초과가 나지 않을 것이라는 생각이 들었고,

이진탐색 개념과 설명을 다시 상기시키고 구글링해가며 코드를 다시 짰다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath> //C++
#include <algorithm>
#include <stack>

using namespace std;

int n, m;	// 전역으로 선언하여 main 외 함수에도 사용 할 수 있도록 함
vector<int> A;
int binarySearch(int k);

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(0); cin.tie(0);     // 시간초과방지

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int tmp;
		scanf("%d", &tmp);
		A.push_back(tmp);
	}
		
	sort(A.begin(), A.end());		// 오름차순 정렬 

	scanf("%d", &m);

	// 오름차순 정렬 후 이진탐색 진행
	for (int i = 0; i < m; i++) {
		int num;
		scanf("%d", &num);
		int result = binarySearch(num);
		printf("%d\n", result);
	}

	return 0;
}
int binarySearch(int k) {
	int l = 0;		// 이진탐색에서 맨 왼쪽 인덱스를 기억할 변수
	int r = n - 1;		// 이진탐색에서 맨 오른쪽 인덱스를 기억할 변수
	int m;

	while (r >= l) {
		m = (l + r) / 2;		// 이진탐색에서 가운데(key, 즉 k)를 기억할 변수, 매번 찾는값이 k가 맞는지 검증

		if (A[m] == k)
			return 1;
		else if (A[m] > k)
			r = m - 1;
		else if (A[m] < k)
			l = m + 1;
	}
	return 0;
}

이진탐색에 관한 자세한 건 주석으로 설명을 달아놓았다.

내가 쓴 방법은 main 함수에서 binarySearch(이진탐색함수)의 반환값(1또는 0)을 받아

받은 반환값을 출력하는 방법이었지만,

 

binarySearch(이진탐색함수)함수 안에서 직접적으로 출력하는,

즉 binarySearch()의 반환값을 void로 지정하고

그냥 그 함수 안에서 찾으면1, 못찾으면 0을 출력하는 방법도 괜찮을 것 같다.

---

깨달은 점

:

내가 떠올린 방법의 시간복잡도가 정말 최선인지 고려해보자.

아무래도 벡터의 전 범위를 도는 것은 오래걸릴 수 밖에 없다.

 

찾고자 하는 원소가 특정할때 이진탐색을 사용하면,

시간복잡도를 O(logN)로 줄일 수 있고, 백준 시간초과를 방지할 수 있다.