[백준] 10816 - 숫자 카드2 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

10816번: 숫자 카드 2

문제

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

접근방법

 문제는 두 번째 줄의 숫자를 정리하여, 4번째에서 요구하는 숫자에 대한 개수 출력을 요구하고 있다. 상근이가 가진 N개의 카드 중 중복되는 숫자를 지닌 카드도 존재한다. 때문에 정렬할 때, 가지고 있는 개수 또한 고려해야 한다.   

풀이

 여러 풀이 방법이 있을 수 있다고 생각이 들었다. 나는 여러 방법 중에 HashMap을 이용하여 문제를 해결했다. Hash란 데이터를 효율적으로 관리하기 위해 특정 길이에 임의의 값을 데이터로 매핑시키는 함수이다.  key-value 구조를 가지며, 검색, 삽입 , 삭제가 빠르다는 장점을 갖고 있다. 이러한 특징이 해당 문제에 적합하여, HashMap을 사용하였다. Key 값으로 카드 숫자, Value 값으로 해당 카드의 개수를 준다면, 쉽게 검색하여, 개수를 수정할 수 있다.  

코드

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 {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        HashMap<Integer, Integer> datas = new HashMap<>();

        //N, N개의 카드 입력
        int N = Integer.parseInt(br.readLine());
        stk = new StringTokenizer(br.readLine(), " ");

        for (int i = 0 ; i < N ; i++){
            int keyNum = Integer.parseInt(stk.nextToken());
            //Map에 삽입, 해당 카드 번호의 데이터를 확인하고 하나씩 추가함
            //Map에 처음 삽입하는 경우 default 0 으로 삽입
            datas.put(keyNum,datas.getOrDefault(keyNum,0)+1);
        }


        //M과 M개의 숫자 입력
        int M = Integer.parseInt(br.readLine());
        int[] targets = new int[M];
        stk = new StringTokenizer(br.readLine()," ");
        for(int k = 0 ; k < M ; k++){
            targets[k] =Integer.parseInt(stk.nextToken());

        }
        
        
        //출력
        System.out.println(solution(datas,targets));


    }

    public StringBuilder solution(HashMap<Integer,Integer> datas, int[] targets){
        StringBuilder sb = new StringBuilder();
        for (int target : targets){
            //존재 하지 않는 값에 대해선 0, 나머지는 빼옴
            sb.append(datas.getOrDefault(target,0)+" ");
        }
        return sb;
    }
}

결과

 위 결과의 속도 차이는 반복문을 어떻게 쓰는 지의 차이였다. (로직의 차이는 없다는 의미이다.)

초기에 HashMap의 메서드인 hasMoreTokens()를 사용하여, 토큰을 모두 뽑아내었다. 그러다 보니 변수 N, M은 입력받아놓고도 쓰지도 않았다. -ㅅ-:

확실히 함수로 접근하는 것이 속도가 느리다는 것을 보여준 문제라고 생각한다.

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.