[Baekjoon] 백준 1920 수 찾기 (S4 / 이분탐색) - Java

링크

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

1920번: 수 찾기

 

 

 

문제 해석

백준 1920 수 찾기
- 문제 해석
N개의 정수가 주어졌을 때, M개의 정수가 각각 N개의 정수에 포함되는지 여부를 구하라


- 입력
첫 번째 줄 : N # 포함 여부를 확인할 자연수 개수
두 번째 줄 : N개의 자연수
세 번째 줄 : M # 찾으려는 수 개수
네 번째 줄 : M개의 자연수 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 비교 대상 숫자 개수
		int[] arr = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);

		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()); // 존재 여부 확인 할 숫자 개수

		int answer;
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int checkNum = Integer.parseInt(st.nextToken());
			answer = 0;

			int start = 0; // 배열의 시작 위치
			int end = arr.length - 1; // 배열의 끝 위치

			while (start <= end) {
				int mid = (start + end) / 2; // 배열의 중간 위치

				// 찾으려는 값보다 배열에 들어가 있는 값이 더 작다면
				if (checkNum > arr[mid]) {
					start = mid + 1;
				}

				// 찾으려는 값보다 배열에 들어가 있는 값이 더 크다면
				if (checkNum < arr[mid]) {
					end = mid - 1;
				}

				// 찾으려는 값과 배열에 들어간 값이 같다면
				if (checkNum == arr[mid]) {
					end = arr[mid];
					answer = 1;
					break;
				}

			}
			System.out.println(answer);

		}

	}
}

 

 

 

코드 해석

이분 탐색의 가장 기본적인 문제가 됩니다.
주어진 N개의 수를 배열에 집어넣고 정렬 후 이분 탐색을 통해 값의 존재 여부를 파악한다면 쉽게 해결할 수 있습니다.

 

 

 

 

발생한 문제 & 해결 방안

이분 탐색을 수행할 때 배열의 값보다 찾으려는 값이 큰 경우 중간 값 n+1을

작은 경우 중간값-1을 해주어야 한다.

+-1을 하지 않으면 시작이 0, 끝이 1과 같은 상황에서 조건이 끝나지 않고 무한 반복하는 일이 발생한다.

 

쉬운 문제더라도 다시 한 번 제대로 읽고, 로직을 짤 수 있도록 노력하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice