태그

10815 숫자카드 - Binary Search

문제 보러 가기

문제를 간단히 설명하자면

N개의 숫자에 대해서 (단 N은 1부터 500000이하) 입력받은 후 다음 M개의 숫자가 입력되어 있는지를 확인하는 것이다.

문제는 숫자 카드에 적혀있는 수가 -10,000,000 부터 10,000,000까지 이기 때문에 boolean형태의 array를 쓰는 것은 불가능하다.

사실 난이도가 낮은 문제라고 생각하는데, 군대 알고리즘 동아리 문제인만큼, 오랜만에 처음부터 알고리즘을 푼다는 마인드로 풀어보았다.

간단히 생각해보면 N개의 숫자를 모두 다 입력받고 확인하기 때문에 N개의 숫자를 정렬해놓고, binary search로 확인하면 된다.

stl sort나 stl binary_search를 이용하면 편리하다.

사용법은 항상 까먹기에 적어놓자면 (진짜 구라안치고 쓸때마다 까먹는거 같다.)
stl vector 사용시에

sort(v.begin(), v.end(), compare) 

이런 식으로 적으면 되고 배열 쓸 경우에는

sort(A, A+N, compare) 이런 식으로 가능하다.

compare는 bool 형식으로 bool compare(int a, int b) {return a > b;} 이런 식으로 적으면 가능하겠다.

물론 bool operator <(Object &object) {
    return this->item < student.item;
}
처럼 써서 쓰는 것도 가능하고.

binary_search 역시 sort랑 방식이 동일하다.

binary_search(A, A+N, value) 와 같이 가능.

물론 나는 내가 직접 짜보자는 마인드로 다르게 만듬.

코드 풀이는 아래와 같음.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <vector>
using namespace std;
 
int A[500005];
 
void merge_sort(int left, int right){
    if (left >= right) {
        return;
    }
    vector<int> v;
    int mid = (left + right) / 2; 
    
    merge_sort(left, mid);
    merge_sort(mid+1, right);
    
    int l = left;
    int r = mid+1;
    while(l<=mid && r<=right) {
        if(A[l] > A[r]) {
            v.push_back(A[r++]);
        }
        else {
            v.push_back(A[l++]);
        }
    }
    while(l<=mid) {
        v.push_back(A[l++]);
    }
    while(r<=right){
        v.push_back(A[r++]);
    }
    
    int idx = 0;
    for(int i=left; i<=right; i++) {
        A[i] = v[idx++];
    }
}
 
bool binary_search(int left, int right, int value) {
    if(left > right) {
        return 0;
    }
    int mid = (left + right) / 2;
    
    if (A[mid] == value) return 1;
    if (A[mid] > value) {
        return binary_search(left, mid-1, value);
    }
    else {
        return binary_search(mid+1, right, value);
    }
    
}
 
 
int main() {
    int N, M;
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);
    merge_sort(0, N-1);
    scanf("%d", &M);
    while(M--) {
        int tmp; scanf("%d", &tmp);
        if(binary_search(0, N-1, tmp)) {
            printf("1 ");
        }
        else{
            printf("0 ");
        }
    }
}
cs
라벨:

댓글

댓글 쓰기

가장 많이 본 글