[Baekjoon] C++ 1920번 - 수 찾기 (Silver 4)

1929번: 수 찾기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

173155

51786

34391

29.842%

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

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

 

정답

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int Search(int* arr, int size, int key);

int main()
{
    cin.tie(NULL);
	ios::sync_with_stdio(false);
    
    int N, M, number;
    int arr[100001];
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    
    // 이진 탐색을 위한 정렬
    sort(arr, arr + N);
    
    cin >> M;
    
    for(int i = 0; i < M; i++) {
        cin >> number;
        
        cout << Search(arr, N, number) << "\n";
    }

    return 0;
}

// arr : 검색할 배열, size : 검색할 배열 사이즈, key : 찾을 값 
int Search(int* arr, int size, int key)
{
    // 맨 앞 인덱스
    int first = 0;
    
    // 맨 끝 인덱스
    int last = size - 1;
    
    // 중간 인덱스
    int middle;
    
    while(first <= last) {
        // 중간 값 설정
        middle = (first + last) / 2;
         
        // 중간 값이 찾고자 하는 값일 경우 1 리턴
        if(arr[middle] == key) {
            return 1;
        }
        // 찾고자 하는 값이 중간 값보다 클 경우 탐색 범위를 우측으로 축소
        else if(arr[middle] < key) {
            first = middle + 1;
        }
        // 찾고자 하는 값이 중간 값보다 작을 경우 탐색 범위를 좌측으로 축소
        else {
            last = middle - 1;
        }
    }
 
    // 값을 찾지 못했을 경우   
    return 0;
}

 

문제 풀이

간단한 수가 있는지 확인하는 내용이다.

 

간단하게 선형 탐색을 이용해서 풀어봤다.

endl을 사용하지 않아도 시간 초과로 실패한다...

 

아래는 실패한 선형 탐색 코드이다.

#include <iostream>
#include <stdio.h>

using namespace std;

bool Compare(int *arr, int size, int key);

int main()
{
    
    cin.tie(NULL);
	ios::sync_with_stdio(false);
    
    int N, M;
    bool result;
    
    int A[100001];
    int arr[100001];
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    cin >> M;
    
    for(int i = 0; i < M; i++) {
        cin >> arr[i];
    }
    
    for(int i = 0; i < M; i++) {
        result = Compare(A, M, arr[i]);
        
        if(result == false) {
            cout << 0 << endl;
        }
        else {
            cout << 1 << endl;
        }
    }

    return 0;
}

bool Compare(int *arr, int size, int key)
{
    int i = 0;
    
    arr[size] = key;
    
    while(1) {
        if(arr[i] == key) {
            break;
        }
        i++;
    }
    
    return i == size ? false : true;
}

 

선형 탐색 알고리즘의 시간은 O(n) 으로 1초에 못미친다.

 

그래서 조금 더 빠른 이진 탐색을 이용해 풀어봤다.

 

이진 탐색으로 시도 시 성공했다.