Menu

Subscribe

[JAVA/백준] 이분 탐색: 숫자 카드 2

HEESOO on Boj, Hash

👀 문제

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

👊 도전

1. 설계

  1. 카드 별 갯수도 세어야하므로 해쉬맵을 사용한다.
  2. key는 숫자, value는 카드 갯수로 하여 n개의 숫자 카드를 저장한다.
  3. m개의 카드를 배열에 저장한 후, 해쉬맵에 있으면 해당 value를 리턴하고, 없으면 0을 리턴한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

/**
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		HashMap<Integer, Integer> map=new HashMap<>();
		for(int i=0;i<n;i++) {
			int temp=scan.nextInt();
			if(map.containsKey(temp))
				map.put(temp, map.get(temp)+1);
			else
				map.put(temp, 1);
		}
		
		int m=scan.nextInt();
		int[] input=new int[m];
		for(int i=0;i<m;i++)
			input[i]=scan.nextInt();
		
		for(int i=0;i<m;i++) {
			if(map.containsKey(input[i]))
				System.out.print(map.get(input[i])+" ");
			else
				System.out.print("0 ");
		}
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 해쉬맵을 사용한다
    • n개의 카드와 그 갯수를 모두 저장해야하므로 처음에는 클래스를 하나 만들거나, 인덱스를 카드 번호로 하고 원소값을 카드 숫자로 하여 계산할까 하다가, 그러면 n개의 카드를 저장하는 과정에서 해당 숫자가 이전에 저장되었는지 또 확인하는 것이 번거로워 해쉬맵을 사용하기로 했다.
    • 해쉬맵은 key가 중복되지 않게 저장하고 value에 해당 갯수를 저장할 수 있다.
    • m개의 숫자 카드를 array에 저장한 후, 해쉬맵에 해당 key가 존재하면 그 value를 출력하고, 없으면 0을 출력한다.

👏 해결 완료!

  • 문제 분류는 이분 탐색이었기 때문에 다른 사람들이 짠 코드를 확인해보았는데, 인덱스를 카드 번호로 하여 구현한 경우가 많았다.