백준 10816: 숫자 2(java)

문제

---

풀이

 

해시맵을 사용한 방법 또는 이분 탐색을 이용한 방법 2가지로 풀이할 수 있다.

---

1. 해시맵 사용

 

카드와 그 카드의 개수를 각각 키와 값으로 가진 해시맵을 사용한다.

if(hm.containsKey(input))
	hm.put(input, hm.get(input)+1);
else
	hm.put(input, 1);

입력된 숫자가 해시맵에 존재하지 않을 경우(=처음으로 등장한 카드일 경우) 지금까지 한 장 등장한 것이므로 해시맵에 <n, 1>을 삽입하고, 입력된 숫자가 해시맵에 이전에 삽입된 적 있는 숫자일 경우 이전보다 한 장 더 등장한 것이므로 (n, (지금까지 해당 카드 개수)+1)을 삽입한다.

if(hm.containsKey(input))
	sb.append(hm.get(input)+" ");
else
	sb.append(0+" ");

이후 해시맵에서 원하는 카드의 장수를 찾아 출력하면 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, Integer> hm=new HashMap<>();
		StringBuilder sb=new StringBuilder();
		
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int input=Integer.parseInt(st.nextToken());
			if(hm.containsKey(input))
				hm.put(input, hm.get(input)+1);
			else
				hm.put(input, 1);
		}
		
		int M=Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int input=Integer.parseInt(st.nextToken());
			if(hm.containsKey(input))
				sb.append(hm.get(input)+" ");
			else
				sb.append(0+" ");
		}
		System.out.println(sb);
	}
}

---

2. 이분 탐색을 활용한 방법

 

이분 탐색으로 n이 처음 등장하는 인덱스와 마지막으로 등장하는 인덱스를 찾아 이 둘의 차를 구하는 방식이다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, Integer> hm=new HashMap<>();
		StringBuilder sb=new StringBuilder();
		
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int input=Integer.parseInt(st.nextToken());
			if(hm.containsKey(input))
				hm.put(input, hm.get(input)+1);
			else
				hm.put(input, 1);
		}
		
		int M=Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int input=Integer.parseInt(st.nextToken());
			if(hm.containsKey(input))
				sb.append(hm.get(input)+" ");
			else
				sb.append(0+" ");
		}
		System.out.println(sb);
	}
}

 

이분 탐색(위)보다 해시맵(아래)가 조금 더 빠른 듯 하다.