[백준] 1920번: 수 찾기 | C++ 풀이

# 문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

 

---

 

# 풀이

이진 탐색 문제! 이진 탐색을 사용하는 첫 문제인만큼 직접 구현한 풀이 하나, algorithm 헤더에 구현된 이진 탐색 함수를 사용한 풀이 하나 총 두 개의 풀이를 업로드하려고 한다.

정답 소스코드를 보며 확인해보자.

 

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

int binarySearch(int len, int m, int arr[]);

int main(){
	ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제
	cin.tie(NULL);	// 입력과 출력 묶음을 풀기

    int n;
    cin >> n;
    int arr[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++){
        int tmp;
        cin >> tmp;
        cout << binarySearch(n, tmp, arr) << ' ';
    }
    return 0;
}

int binarySearch(int len, int m, int arr[]){
    int start = 0;
    int last = len-1;
    int midIdx;

    while(start <= last){
        midIdx = (start + last) / 2;
        if(m == arr[midIdx]) return 1;
        else if(m < arr[midIdx]) last = midIdx-1;
        else start = midIdx+1;
    }
    return 0;
}

해당 코드에서는 이진 탐색을 수행하는 binarySearch 함수를 만들어주었다.

 

 

 

int binarySearch(int len, int m, int arr[]){
    int start = 0;
    int last = len-1;
    int midIdx;

    while(start <= last){
        midIdx = (start + last) / 2;
        if(m == arr[midIdx]) return 1;
        else if(m < arr[midIdx]) last = midIdx-1;
        else start = midIdx+1;
    }
    return 0;
}

해당 코드는 매개변수로 배열, 배열의 길이, 탐색할 숫자인 m을 받는다.

이진 탐색의 인덱스 설정을 위해 start, last, midIdx 변수를 각각 선언 및 초기화 해주면 준비 끝이다.

while문을 돌며 탐색을 수행하는데 만약 찾는 값이 배열의 중간값과 같다면 바로 1을 return, 작거나 크다면 start와 last 인덱스의 값을 수정해준다. 이때 인덱스를 잘못 설정하면 무한 루프에 빠지는 문제가 발생하기도 하니 이해가 안 간다면 손으로 예시를 넣어보며 확인하자.

while문을 다 돌고 나왔다면 탐색하는 값이 배열 내에 존재하지 않는다는 의미이므로 0을 리턴해준다.

 

 

 

int n;
cin >> n;
int arr[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++){
    int tmp;
    cin >> tmp;
    cout << binarySearch(n, tmp, arr) << ' ';
}
return 0;

다음은 main 함수다. n개의 정수가 주어지므로 n을 받아와 n을 크기로 한 배열을 만들어준다.

그리고 for문을 돌며 값을 넣어준 후 이진 탐색을 위해 sort하면 준비 끝!

m개의 숫자에 대해 탐색을 진행할 것이므로 값을 받아와 for문의 인덱스로 주고, 반복문을 돌며 해당 값에 대한 binarySearch를 수행하여 결과를 출력하면 된다.

 

 

 

 

---

 

 

# 풀이 2 

이번엔 앞서 말했듯 algorithm 헤더에 미리 구현되어 있는 binary_search 함수를 가져다 사용해 풀이를 해보려고 한다.

 

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

int main(){
    ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제
    cin.tie(NULL);	// 입력과 출력 묶음을 풀기

    int n;
    cin >> n;
    int arr[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++){
        int tmp;
        cin >> tmp;
        if(binary_search(arr, arr+n, tmp)) cout << 1 << ' ';
        else cout << 0 << ' ';
    }
    return 0;
}

n개의 숫자를 받아와 배열에 넣고 정렬해주는 것까지는 풀이 1과 동일하다.

탐색 과정에서 이번에는 binary_search를 사용하는데 배열의 시작, 끝, 탐색할 값을 넣어주면 된다. 더 자세히 알아보고 싶다면 키워드에 걸어둔 레퍼런스 링크에 들어가 읽어보길 권한다.

 

간단히 살펴보면 아래와 같이 동작하는 함수다.

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

반환 값이 bool 타입이므로 true가 반환되면 1을 출력, false가 반환되면 0을 출력해주면 끝이다.

 

 

 

---

 

 

위의 실행 결과가 풀이1, 아래의 실행 결과가 풀이 2다.

메모리나 시간 측면에서도 차이가 없으니 동작 과정만 이해하고 구현된 함수를 쓰는 게 좋지 않을까...?

 

 

 

---

 

 

 

1920번: 수 찾기