공부 자료/알고리즘
(C/C++) 백준 1920번 - 수 찾기
뚜루뚜루세니
2021. 7. 26. 11:53
728x90
문제 출처: https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
1. 코드
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arrN[100001];
int arrM[100001];
void find(int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2; //중간 값 인덱스
if (arrN[mid] == key) { //수가 같으면
printf("1\n");
return;
}
else if (arrN[mid] > key) { // key값이 배열의 중앙 값보다 작을때 = 왼쪽으로
right = mid - 1;
}
else { //key의 배열이 중앙값보다 클때 = 오른쪽으로
left = mid + 1;
}
}
printf("0\n");
return;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arrN[i]);
}
sort(arrN, arrN + n);//오름차순 정렬
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d", &arrM[i]);
find(n, arrM[i]);
}
}
|
cs |
2. 해결 과정
이진 탐색을 이용하여 문제를 풀면 된다. 처음에 n개의 수를 배열에 입력받고, 오름차순으로 정렬시켜준다.
m개의 수를 입력받고 배열에 저장하며, 탐색을 시작한다.
가장 마지막 인덱스 값을 right으로 설정해주고, 가장 처음의 인덱스 값을 left로 설정해준다. mid값은 두 left와 right를 더해서 2로 나눈 값으로 중앙값이라고 말할 수 있다.
만약에 key값과 mid값이 같으면 1을 출력해주면 되고, key값이 배열의 중앙값보다 작으면 중앙값에서 1을 뺀 것이 right값이 된다.
만약에 key값이 배열의 중앙값보다 크다면 left값이 중앙값+1해준 값이 된다.
up&down 게임이랑 비슷하다고 생각하면 쉽게 풀린다.
3. 느낀점
백준 10815번 숫자 카드 문제와 거의 비슷한 문제여서 쉽게 풀렸다. 이진 탐색을 사용하면 쉽게 값을 찾을 수 있었다. 개념을 배우고 나서 문제를 푸니 더 쉽게 풀렸던 것 같다.
728x90