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(num<arr[center]) {
					max=center-1;
				}else { // num==arr[center]일 경우
					System.out.println(1);
					return;
				}
			} //끝날때까지 답을 찾지 못한 경우 0을 출력
			System.out.println(0);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		arr = new int[N];
		for(int i=0; i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr); //N개의 값을 입력 받고 배열에 넣고 정렬
        
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<M;i++) { //M을 받고 M개의 수들을 판별
			int find = Integer.parseInt(st.nextToken());
			if(find>arr[N-1] || find<arr[0]) {
				System.out.println(0); // 경계값 밖의 값이면 0출력
			}else {
				match(find); //경계값 안의 값이면 메소드 실행
			}
		}
}}