[백준]10815번 숫자 카드(java)

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

10815번: 숫자 카드

백준 10815번 숫자 카드 문제 링크입니다.

 

핵심

처음 입력된 숫자 중에서 상근이가 가지고 있는 숫자가 있으면 1 아니면 0을 출력하는 것이다. 처음에는 contains를 사용하여, 포함 여부를 확인해보았는데, 이는 시간이 너무 오래 걸려서 시간 초과가 떴다. 이문제는 binarySearch를 사용하는 것이 핵심이다. 

 

정답 코드

 

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

public class Main {
	public static void main(String[] args) throws Exception{
		int N,M=0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		String[]strNum=br.readLine().split(" ");
		M = Integer.parseInt(br.readLine());
		String[]strmNum=br.readLine().split(" ");
		StringBuilder sb = new StringBuilder();
		Arrays.sort(strNum);

		for(int j=0;j<M;j++){
			sb.append((Arrays.binarySearch(strNum,strmNum[j])>=0)?1+" ":0+" ");
		}
		System.out.print(sb);
	}

}

 

해설

사실 N 은 아무 역할을 하지 않는데, 입력의 형식을 맞추기 위해 사용되었다.

각 배열에 split을 사용하여, 공백마다 숫자를 구분하였다.

이후 제시되는 숫자 배열을 정렬한다. 

그다음 binarySearch를 사용하여 상근이의 카드가 제시된 숫자를 포함하였는지 확인한다.

binarySearch를 사용하기 위해서는 반드시 정렬된 상태여야 한다. 

만약 상근이의 카드가 제시된 숫자를 포함한다면, 0 이상의 값을 반환하고, 포함하지 않았다면 음수를 반환한다.

즉 0 이상이면 sb에 1을 추가하고 음수이면 0을 추가한다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.