[백준BOJ] 10815번 숫자 카드.java

 

백준 저지에서 숫자 카드를 자바를 통해 풀어 보았다. 

 

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

10815번: 숫자 카드

10815번 숫자 카드.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

10815번 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

설명

숫자 카드들 중 찾고자 하는 숫자가 있는지 없는지 판단해야 한다. 즉 숫자 배열에서 어떤 숫자가 있는지 확인한다. 단 카드의 범위가 크기 때문에 완전 탐색보다는 빠른 탐색 알고리즘이 필요하다.

 

이에 대해 이분 탐색을 활용해서 풀었다. 먼저 숫자 카드 배열을 오름차순으로 정렬해준 후 이분 탐색을 통해 찾고자 하는 카드가 있는지 확인했다.

코드

//10815번 숫자 카드.java
package week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 숫자_카드_10815 {
	private static int N;
	private static int M;
	private static int[] card;
	private static int[] num;
	public static void main(String[] args) throws NumberFormatException, IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		card = new int[N];
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line," ");
		for(int i=0;i<N;i++) {
			card[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(card);
		M = Integer.parseInt(br.readLine());
		num = new int[M];
		line = br.readLine();
		st = new StringTokenizer(line," ");
		for(int i=0;i<M;i++) {
			int checkNum = Integer.parseInt(st.nextToken());
			num[i]=searchNum(checkNum);
			sb.append(num[i]).append(" ");
		}
		System.out.println(sb.toString());
	}
	public static int searchNum(int num) {
		int left = 0;
		int right = card.length-1;
		int mid = (left+right)/2;
		while(left<=right) {
			if(card[mid]<num) {
				left=mid+1;
				mid = (left+right)/2;
			}
			else if(card[mid]>num) {
				right = mid-1;
				mid = (left+right)/2;
			}
			else {
				break;
			}
		}
		if(card[mid]==num)return 1;
		else return 0;
	}
}