[백준 1920번 / JAVA] 수 찾기

[백준 1920번 / JAVA] 수 찾기코딩테스트/백준2023. 6. 21. 10:23@mag1c

Table of Contents

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

서론

지조있게(?) 프로그래머스 업로드를 기다리다가 드디어 포기하고 백준에 입문하게 되었다.

찾아보니 작년 12월에 풀었던 이력이 있었으며, 그 때는 백준에서의 테스트 포맷이 프로그래머스와 너무 달라 입출력에 난항을 겪어 후퇴했던 기억이 있다.

하지만 leetcode와 hackerrank로 단련된 지금, 백준을 통해 꾸준히 문제를 풀어 나가려고 한다.

풀이

N의 범위가 1~100,000이었기 때문에 이분탐색을 활용하여 풀었다.

잊을만하면 등장하는 것 같다. 아래는 내가 처음 이분탐색을 접했을 때 공부한 내용

[알고리즘] 이진탐색(이분탐색) - Binary Search

Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는

mag1c.tistory.com

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main{
	
    public static void main(String[] args) throws IOException{    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	int[] Narr = new int[N];    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	for(int i=0; i<N; i++) {
    		Narr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(Narr);
    	    	
    	int M = Integer.parseInt(br.readLine());
    	st = new StringTokenizer(br.readLine(), " ");
    	StringBuilder sb = new StringBuilder();
    	for(int i=0; i<M; i++) {
    		int mdouble = Integer.parseInt(st.nextToken());
    		
    		if(binarySearch(mdouble, Narr) >= 0) {
    			sb.append("1");
    		}
    		else sb.append("0");
    		
    		sb.append("\n");
    		
    	}
    	
    	System.out.println(sb);
    
    }

	private static int binarySearch(int mdouble, int[] Narr) {
		int left = 0;
		int right = Narr.length-1;
		
		while(left <= right) {
			int mid = (left + right) / 2;
			
			if(mdouble < Narr[mid]) right = mid - 1;
			else if(mdouble > Narr[mid]) left = mid + 1;
			else return mid;
		}
		
		return -1;
	}

}

728x90