[C++] 백준 1920번 수 찾기 :: seoftware

문제

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
int arrA[100000];
int arrB[100000];
int result[100000];
int main(void) {
	//input
	int N, M;
	scanf("%d", &N);
	for (int n = 0; n < N; n++) {
		scanf("%d", &arrA[n]);
	}
	scanf("%d", &M);
	for (int m = 0; m < M; m++) {
		scanf("%d", &arrB[m]);
	}
    //perform
	sort(arrA, arrA + N);
	for (int m = 0; m < M; m++) {
		int head = 0;
		int tail = N-1;
		int mid;
		while (head <= tail) {
			mid = (head + tail) / 2;
			if (arrB[m] == arrA[mid]) {
				result[m] = 1; break;
			}
			else if (arrB[m] > arrA[mid]) {
				head = mid+1;
			}
			else {
				tail = mid-1;
			}
		}
        //output
		printf("%d\n", result[m]);
	}

}

 

코드설명

 

1. N개의 요소를 가지는 A배열과 M개의 요소를 가지는 B배열을 입력받는다.

2. A배열을 정렬한 후 이분탐색을 이용하여 B배열의 요소가 A에 있는지 탐색한다. 

이분탐색이란 배열에서 어떤 수를 찾을 때 찾는 범위를 반씩 줄여나가는 탐색 방법이다.

0. 배열 A가 [6, 1, 4, 2, 3, 5] 으로 구성되어 있고, 여기서 2(target)를 찾는다고 가정해보자.

1. 배열 A를 정렬한다 -> [1, 2, 3, 4, 5, 6]

2. 시작 인덱스, 끝 인덱스, 중간 인덱스를 잡는다 -> 시작 = 0, 끝 = 5, 중간 = 2

3. A[중간인덱스] (=A[2]) 와 target을 비교한다. A[2]는 3이고, target은 2이므로 target이 중간지점보다 앞에 위치하는 것을 알 수 있다(배열에 없을 수도 있다.)

4. 따라서, 끝 인덱스를 (중간인덱스 - 1)로 잡는다. 만약 target이 A[2]와 같았다면 탐색이 완료되는 것이고, target이 A[2]보다 컸다면 시작인덱스를 (중간인덱스 + 1)으로 새롭게 설정한다.


5. 시작인덱스가 끝인덱스보다 커지지 않는 조건에서 2번에서 4번 과정을 반복한다.

3. 이분탐색으로 target이 찾아지면 result[m]의 값을 1로 변경한다. result 배열은 전역변수로 선언했기 때문에 0으로 초기화되어 있으므로 값이 변경되지 않았다면 0을 출력하게 된다.