백준 10816: 숫자 카드 2(JAVA)

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

10816번: 숫자 카드 2

전에 풀었던 숫자 카드는 해당 숫자의 카드가 있는지만 판별하면 되는거라서 HashSet의 contains로 쉽게 풀 수 있었다.

이번 숫자 카드 2 문제는 해당 숫자의 카드가 몇 개 있는지까지 저장해야해서 위와 같은 방법으로는 풀 수 없다. 그래서 떠올린 방법이 map을 이용하는 것이다. 물론 더 좋은 방법이 있을 것 같지만...일단 도전

 

key 값으로 카드의 숫자, value 값으로 해당 숫자 카드의 개수를 담았다.

시간 단축을 위해 StrigBuilder를 사용하였다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		int N, M;
		Integer k, v = 0;

		Scanner sc = new Scanner(System.in);
       		StringBuilder sb = new StringBuilder();
		N = sc.nextInt();

		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<N; i++){
			k=sc.nextInt();
			v=map.get(k);
			if(v==null)
				map.put(k, 1);
			else {
				v++;
				map.replace(k, v);
			}
		}

		M=sc.nextInt();

		for(int i=0; i<M; i++) {
			k=sc.nextInt();
			v=map.get(k);
			if(v!=null) {
				sb.append(v+" ");
			}else
				sb.append("0 ");
		}
        	System.out.println(sb);
	}
}

풀리긴 풀린다

 

그리고 두번 째 방법으로는 앞에 풀었던 수 정렬하기 3 문제에서 사용하였던 계수 정렬(counting sort)을 이용하는 것이다. 숫자의 범위가 -10000000~10000000이라 배열의 크기를 2000001이나 잡아야 해서 메모리를 많이 차지하지만 속도는 좀 더 빠르다. 

import java.util.*;

public class Main {

	public static void main(String[] args){
		int N, M;
		int[] arr = new int[20000001];
		int n;

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		N = sc.nextInt();

		for(int i=0; i<N; i++) {
			n = sc.nextInt();
			arr[n+10000000]++;
		}

		M = sc.nextInt();

		for(int i=0; i<M; i++) {
			n = sc.nextInt();
			sb.append(arr[n+10000000]+" ");
		}
		System.out.println(sb);
	}
}

BufferedReader 사용하면 더 빠를 것 같다. 아직 사용법이 익숙치 않아서 공부를 좀 더 해야겠다.

다른 사람들의 풀이를 보니 나와 비슷하게 푼 사람들이 꽤 많다. 근데 이분탐색을 응용한 풀이가 많다. 정답이 정해져있는 것은 아니지만 이분탐색 풀이법이 좋아보인다. 공부를 하고 다시 풀어봐야지