[BOJ]10816_숫자카드2_Java

--문제--

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

10816번: 숫자 카드 2

--문제 접근--

이분 탐색과 hashmap으로 문제로 풀이가 가능한데 이분 탐색이 익숙해지기 위해 분류별로 이분 탐색으로 풀고 있으므로 이분 탐색으로 풀이를 진행해 봤습니다. 이분 탐색 중복 cnt 하는 방법을 몰라 upperbound와 lowbound를 검색해서 풀이를 진행했습니다.

똑같은 코드여도 스캐너로 진행하면 시간초과가뜨고 BufferedReader를 사용하면 통과하는 모습을 보니 이제 BufferedReader를 자주 사용해야 할 것 같다고 생각했습니다..ㅜㅜ

package 백준문제풀이;

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

public class BOJ_10816_숫자카드2 {
	static int N;
	static int[] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
//		Scanner sc=new Scanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb=new StringBuilder();
		N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		map=new int[N];
		for(int i=0;i<N;i++) {
			map[i]=Integer.parseInt(st.nextToken());
		}
		int M=Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine());
		Arrays.sort(map);
		for(int i=0;i<M;i++) {
			int target=Integer.parseInt(st.nextToken());
			sb.append(upper(target)-low(target)+" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private static int upper(int value) {
		int start=0;
		int end=map.length-1;
		int mid=0;
		while(start<end) {
			mid=(start+end)/2;
			if(value<map[mid])end =mid;
			else {
				start=mid+1;
			}
		}
		if(map[end]==value)end++;//맨끝 배열에 위치한다면 1을 추가해줘야한다.0부터시작하니 이런현상이 나오는거 같다.
		return end;
		
	}

	private static int low(int value) {
		int start=0;
		int end=map.length-1;
		int mid=0;
		while(start<end) {
			mid=(start+end)/2;
			if(value<=map[mid])end =mid;
			else {
				start=mid+1;
			}
		}
		return end;
		
	}


}

--Hash/실패 코드--

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int N=sc.nextInt();
		int[] arr=new int[N];
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0;i<N;i++) {
			int key=arr[i]=sc.nextInt();
			if(map.containsKey(key))map.put(key, map.get(key)+1);
			else map.put(key,1);
		}
		
		int M=sc.nextInt();
	
		for(int i=0;i<M;i++) {
			int a=sc.nextInt();
			int ans=(map.get(a)==null)? 0:map.get(a);
			System.out.print(ans+" ");
		}
				
		
	}
}