[백준/C++] 1920번 수 찾기

문제: www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

문제풀이

 

이진 탐색 문제이다. 배열을 정렬한 후 이진 탐색을 진행하면 된다.

 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

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

    int N;
    cin>>N;

    int A[N];
    for(int i=0; i<N; i++)
        cin>>A[i];

    sort(A, A+N); //오름차순 정렬

    int M;
    cin>>M;

    int num;
    while(M--){
        cin>>num;

        int start=0;
        int end=N-1;
        bool findNum = false; //탐색 중 수를 찾았는지 여부를 나타내는 논리 변수
        while(start<=end){
            int mid = (start+end)/2;

            if(num == A[mid]){ //수를 찾았으면 1 출력
                cout<<1<<"\n";
                findNum = true;
                break;
            }
            else if(num > A[mid]){
                start=mid+1;
            }
            else{
                end = mid-1;
            }
        }
        if(!findNum) //수를 찾지 못했으면 0 출력
            cout<<0<<"\n";
    }

    return 0;
}

 

 

결과

 

문제를 잘 못 이해서 엄청 고생했습니다.

알고리즘 문제를 풀 땐 짧은 문제라도 정확히 문제를 이해하고 풀이를 시작하는 것이

가장 중요한 것 같습니다...