[BOJ-1920][이분탐색] 수 찾기 -Java

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

1920번: 수 찾기

package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.StringTokenizer;

public class boj_1920_수찾기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N=Integer.parseInt(st.nextToken());
		HashSet<Integer> set= new HashSet<>();
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			set.add(Integer.parseInt(st.nextToken()));
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int M=Integer.parseInt(br.readLine());
		st= new StringTokenizer(br.readLine());		
		for(int i=0; i<M; i++) {
			if(set.contains(Integer.parseInt(st.nextToken()))) bw.write("1\n");
			else bw.write("0\n");
		}
		
		bw.flush();
		
	}

}

소요시간 : 15분

 

백준에서 카테고리는 이분탐색으로 되어있는데 다른방법으로 풀 수 있을 것 같아서 다른방법으로 풀었습니당.

 

제한조건을 살펴보면 N x M 으로 탐색하게 되면 시간초과가 납니당

• N(1 ≤ N ≤ 100,000)
• M(1 ≤ M ≤ 100,000)

 

이분탐색으로 풀기 위해서는 N을 정렬시켜 nlog n의 복잡도로 풀 수 있습니당

 

 

제가 푼 방식을 설명드리자면 Set을 이용해서 N의 값을 다 담아줍니다.

그 후 M을 하나씩 순회하며 Set에 포함이 되어있는지 확인해 줍니다.

 

그런데, System.out.println을 통해 print를 해주면 시간이 오래 걸려 시간초과가 납니다.

그래서 BufferedWriter를 통해 저장해두었다가 flush()를 통해 한번에 쫙 출력해주면 시간초과를 피할 수 있습니다~

 

끝~