개요
백준 문제 10815번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 30분
https://www.acmicpc.net/problem/10815
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다.
상근이는 숫자 카드 N개를 가지고 있다.
정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
코드
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
| #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> num;
void binSearch(int N)
{
int i,j;
int M = 0;
int mid = 0;
int obj;
int searched = 0;
cin >> M;
for(int k=0;k<M;k++)
{
cin >> obj;
if(k != 0)
{
cout << " ";
}
i = 0;
j = N-1;
searched = false;
while(i <= j)
{
mid = (i + j)/2;
if(obj == num[mid])
{
searched = 1;
break;
}
else if(obj > num[mid])
{
i = mid+1;
}
else
{
j = mid-1;
}
}
cout << searched;
}
}
void solve()
{
int obj;
int val = 0;
int N;
cin >> N;
for(int i=0;i<N;i++)
{
cin >> val;
num.push_back(val);
}
sort(num.begin(),num.end());
binSearch(N);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
|
풀이
탐색 -> 빠른 탐색 알고리즘인 이진 탐색 사용
이진 탐색 사용할려면 정렬해야함 -> 이번에는 sort() 사용
배울 점, 메모
1
2
| ios_base::sync_with_stdio(0);
cin.tie(0);
|
위 코드 안써서 시간초과남
부담갖지말고 매일매일 하루를 채운다는 느낌