[백준 10815] 숫자 카드 - JAVA

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

문제 설명

---

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

문제 접근

---

• 문제 자체는 어렵지 않았다. 상근이가 가진 카드 배열을 만들고, 비교할 숫자가 상근이의 카드 목록에 있는지 확인만 하면 된다.
• 대부분 실패 원인이 시간 초과이므로 시간 효율을 신경쓴다.
• 리스트를 만들어서 contains 메소드를 쓰면 간단하나, 그 경우 서치 시간이 O(n)이라 시간 초과가 뜬다.
• 시간복잡도가 O(logN)인 Binary search를 구현한다.
• 입출력도 상대적으로 시간이 덜 걸리는 방법을 쓴다.

문제 풀이

---

public class Main {
	static int[] card;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		N = Integer.parseInt(br.readLine());
		card = new int[N];
		String[] temp = br.readLine().split(" ");
		for(int i=0; i<N; i++) {
			card[i] = Integer.parseInt(temp[i]);
		}

스캐너를 쓰지 않고 버퍼리더로 입력 받는다. 카드의 개수인 N과 카드 목록을 읽어온다.

		Arrays.sort(card);
		
		StringBuilder result = new StringBuilder();
		int M = Integer.parseInt(br.readLine());
		temp = br.readLine().split(" ");
		for(int i=0; i<M; i++) {
			int num = binarySearch(Integer.parseInt(temp[i]));
			result.append(num + " ");
		}
		bw.write(result+"\n");
		bw.close();
		br.close();
	}

바이너리 서치를 위해 카드 목록을 정렬해준다.

비교할 카드 개수와 카드 넘버를 받아오고, 카드가 있는지 검사해 스트링빌더에 더해준다. 처음에는 여기서 빌더 없이 서치 함수에서 문자열을 리턴해 문자열에 바로바로 더해주는 식으로 했더니 시간초과가 떴다.

	private static int binarySearch(int num) {
		int start = 0;
		int end = N-1;
		
		while(start <= end) {
			int index = (start+end)/2;
			if(card[index] == num) {
				return 1;
			}
			else if(card[index] < num) {
				start = index+1;
			}
			else {
				end = index-1;
			}
		}
		return 0;
	}

서치 함수는 정석 방법대로 start와 end, mid(index)를 이용해 카드 배열을 탐색한다. 찾으면 1을 리턴, 찾지 못하면 0을 리턴한다.

전체 코드

---

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

public class Main {
	static int[] card;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		N = Integer.parseInt(br.readLine());
		card = new int[N];
		String[] temp = br.readLine().split(" ");
		for(int i=0; i<N; i++) {
			card[i] = Integer.parseInt(temp[i]);
		}
		Arrays.sort(card);
		
		StringBuilder result = new StringBuilder();
		int M = Integer.parseInt(br.readLine());
		temp = br.readLine().split(" ");
		for(int i=0; i<M; i++) {
			int num = binarySearch(Integer.parseInt(temp[i]));
			result.append(num + " ");
		}
		bw.write(result+"\n");
		bw.close();
		br.close();
	}

	private static int binarySearch(int num) {
		int start = 0;
		int end = N-1;
		
		while(start <= end) {
			int index = (start+end)/2;
			if(card[index] == num) {
				return 1;
			}
			else if(card[index] < num) {
				start = index+1;
			}
			else {
				end = index-1;
			}
		}
		return 0;
	}
}

결과 및 평가

---

살짝 궁금해서 이것저것 해봤는데, contains-> 시간초과, 버퍼 안 씀-> 시간초과, 스트링빌더 안 씀-> 시간초과... 가 떴다.

더 줄이는 방법은 모르고 실패하는 방법만 여럿 알았다. 쓸데없는 짓이라고는 절대 생각하지 않는다! 시간 줄일 때 고려해서 써먹어야지