Baekjoon1920: *수 찾기

Baekjoon1920: *수 찾기

수 찾기

1 초 128 MB 111974 33128 21892 30.185%

문제 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을 출력한다.

풀이

정수의 범위가 2의 31승으로 매우 크다. 즉 카운팅 배열을 사용하는 것은 힘들다.

배열에 값들을 집어넣고 정렬한 뒤 절반 절반 계속 쪼개가며 값을 탐색한다.

1) 값들을 집어넣고 받은 N개의 입력값들을 정렬한다.

arr[N] → Arrays.sort(arr);

2) 오름차순으로 정렬하면 맨 왼쪽이 최소값, 맨 오른쪽이 최대값이 된다.

arr[0]보다 작거나 arr[N-1]보다 크면 경계 밖의 값이므로 찾을 필요없이 0이된다.

3) 배열 안 쪽의 값인 경우 메소드를 사용해 그 값을 판별한다

메소드

M개의 입력값의 수들을 하나하나 판별한다. M의 임의의 수에 대해서 탐색을 시작하는데 arr[N]배열을 탐색한다.

탐색 시작점 = 0, 탐색 끝점 = N-1 로 설정한다

계속해서 현재 시작점과 끝점을 절반을 쪼개가며 탐색한다.

중간점 = (시작점+끝점)÷2 이다.

center는 곧 (min+max)÷2 이며 이것을 배열의 순서에 대입한 arr[center]와 현재 num과 비교해주어야 한다.

while 문 안에서 만약 min과 max의 순서가 뒤바뀌면 (min>max가 된다면) 모두 탐색한 것이므로 반복문을 종료한다.

num 과 arr[center]비교

찾고자 하는 숫자 num이 arr[center] 보다 크면 시작점 min = center+1 로 바꿔주고

찾고자 하는 숫자 num이 arr[center] 보다 작으면 끝점을 max = center-1 로 바꿔준다

* 1을 더하고 빼주는 이유는 무한 루프에 빠질 수 있기 때문이다

만약 num이 arr[center]와 같다면 값을 찾은 것이므로 "1"을 출력해준다

반복문이 종료될 때까지 값을 찾지 못하면 "0"을 출력한다.

import java.io.*; import java.util.*; public class Main { static int[] arr; static void match(int num) { int min=0; //탐색 시작점 =0 int max=arr.length-1; //탐색 끝점 = N-1 while(min<=max){ int center = (min+max)/2; if(num>arr[center]) { min=center+1; }else if(numarr[N-1] || find

from http://devyoseph.tistory.com/184 by ccl(A) rewrite - 2021-12-10 19:27:53