백준 10816. 숫자 카드 2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

문제제목 : 숫자카드2

문제유형 : 이분탐색

문제난이도 : 실버 4

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

아이디어

처음에는 이분탐색 문제여서 이분탐색을 활용해서 문제를 풀었다. 하지만 똑같은 카드를 가지고 있는 것도 세야하기 때문에, 이분탐색으로 탐색하는 숫자를 찾았을 경우, 왼쪽과 오른쪽을 순차적으로 탐색하여 인덱스를 구해서 개수를 세었는데 시간초과가 났다....... 어떻게든 시간을 줄여보려고 이 코드 저 코드 작성했지만... 계속 시간초과를 해결할 수 없어서 다른 블로그를 참고하여 풀이하였다.  처음부터 찾는 값의 처음과 끝의 인덱스를 구해서 개수를 구해주었다.

 

코드(블로그 참고)

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

public class BOJ10816 {
	public static int[] count;
	public static int N;
	public static int[] card;
	
	public static void main(String[] args) throws Exception {
		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[] card_input = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			card[i] = Integer.parseInt(card_input[i]);
		}
		
		int M = Integer.parseInt(br.readLine());
		int[] M_card = new int[M];
		
		// 주어진 카드 입력
		String[] card2_input = br.readLine().split(" ");
		for (int i = 0; i < M; i++) {
			M_card[i] = Integer.parseInt(card2_input[i]);
		}
		
		Arrays.sort(card); // 정렬
		
		count = new int[M]; // 카운트
		
		for (int i = 0; i < M; i++) {
			int left = find_left(M_card[i]);
			int right = find_right(M_card[i]);
			count[i] = right - left;

		}
		for (int i = 0; i < M; i++) {
			bw.write(String.valueOf(count[i]) + " ");
		}
		bw.flush();
		bw.close();
	}
	
	public static int find_left(int value) {
		int start = 0;
		int end = card.length;
		
		while (start < end) {
			int mid = (start + end) / 2;
			if (card[mid] >= value) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return end;
	}
	
	public static int find_right(int value) {
		int start = 0;
		int end = card.length;
		
		while (start < end) {
			if (start == end) return -1;
			int mid = (start + end) / 2;
			
			if (card[mid] > value) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return start;
	}
}

코드(이분탐색 (시간초과))

 

package week5;

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

public class BOJ10816 {
	public static int[] count;
	public static int N;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		int[] card = new int[N];
		
		// 가지고 있는 카드 입력
		String[] card_input = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			card[i] = Integer.parseInt(card_input[i]);
		}
		
		int M = Integer.parseInt(br.readLine());
		int[] M_card = new int[M];
		
		// 주어진 카드 입력
		String[] card2_input = br.readLine().split(" ");
		for (int i = 0; i < M; i++) {
			M_card[i] = Integer.parseInt(card2_input[i]);
		}
		
		Arrays.sort(card);
		
		count = new int[M]; // 카운트
		for (int i = 0; i < M; i++) {
			find(card, 0, card.length - 1, M_card[i], i);
		}
		for (int i = 0; i < M; i++) {
			bw.write(String.valueOf(count[i]) + " ");
		}
		bw.flush();
		bw.close();
	}
	
	public static void find_adj_left(int[] card, int start, int value, int index) {
		if (start >= 0 && card[start] == value) {
			count[index]++;
			find_adj_left(card, start - 1, value, index);
		}
	}
	
	public static void find_adj_right(int[] card, int start, int value, int index) {
		if (start < N && card[start] == value) {
			count[index]++;
			find_adj_right(card, start + 1, value, index);
		}
	}
	
	public static void find(int[] card, int start, int end, int value, int index) {
		if (start > end) return;
		int mid = (start + end) / 2;
		
		if (card[mid] == value) {
			count[index]++;
			find_adj_left(card, mid - 1, value, index);
			find_adj_right(card, mid + 1, value, index);
		} else if (card[mid] > value) {
			find(card, start, mid - 1, value, index);
		} else {
			find(card, mid + 1, end, value, index);
		}
	}
}