[백준] 1920번 문제풀이

스캐너를 사용하면 시간초과가 나와서 BufferdReader로 하시는 걸 추천 드립니다.

이분탐색 or TreeSet 으로 풀면 되는데 저는 TreeSet 으로 풀었습니다. (다르게 푸신 분도 있겠죠?)

 

* TreeSet은 자동 정렬 기능이 있으며 중복 값을 허용하지 않습니다.*

처음에는 이 점을 이용해서 add만 사용하여 반환되는 T/F 값으로 코드를 짰다가 논리오류 잡는데 시간을 너무 많이써서 다른 방법으로 전환했습니다.

 

코드를 보기 전에 TreeSet에 관련된 메소드를 모르시면 간단하게 보시고 가시면 됩니다.

 

first() : 가장 작은 값을 반환한다.

last() : 가장 큰 값을 반환한다.

floor() : 주어진 값과 동일하거나 그보다 작은 값 중 가장 큰 값을 반환한다.

 

자세한 설명은 코드에 주석을 달아놓았습니다.

 

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


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));	
		TreeSet<Integer> ts = new TreeSet<>();
		
		String[] a = new String[100000]; //문제에서 주어진 자연수 N의 범위
		String[] b = new String[100000]; //문제에서 주어진 M의 범위
		
		int n = Integer.parseInt(bf.readLine()); //N의 길이
		
		a = bf.readLine().split(" "); //공백으로 잘라 배열에 넣기
		
		for(int i =0 ; i<n; i ++) {
			ts.add(Integer.parseInt(a[i])); // TreeSet에 추가
		}
		int m = Integer.parseInt(bf.readLine()); //M의 길이
		
		b = bf.readLine().split(" "); //공백으로 잘라 배열에 넣기
		for(int i =0 ; i<m; i ++) {  //우리가 출력해야할(검사해야할) 문장의 수는 M의 길이와 같음
			if(ts.first()>Integer.parseInt(b[i])) { //(에러방지용)TreeSet에 들어가 있는 수 보다 b[i]가 더 작다면 nullPoint 에러가 발생
				bw.write("0");						//여기 if문만 지워보시고 N의 길이 1, 입력자연수1, M의 길이2, 입력자연수 2, 2 <- 이렇게 넣어보시면 에러납니다.!
			}
			else {
				int ret = ts.floor(Integer.parseInt(b[i])); //b[i]의 값으로 주어진 값과 같거나 작은 값을 TreeSet에서 꺼내어 ret에 저장
				
				if(ret==Integer.parseInt(b[i])) { //TreeSet에서 꺼낸 값 ret와 현재 b[i]의 값이 같다면
					bw.write("1");
				}else {
					bw.write("0");
				}
			}
				bw.flush();
				bw.newLine();	
		}
		bf.close();
		bw.close();
		
	}//end main
}//end Main