🔥[99클럽 코테 스터디] 14일차 TIL - 숫자 카드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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

입출력 예

예제 입력 1

6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1

3 0 0 1 2 0 0 2

---

✏️풀이

일단 문제 내용 자체는 어제의 문제와 유사하다.

최종 코드

다만, 이번에는 입력 값으로 중복이 허용되고, 갯수를 count해야 하는 문제이기 때문에,
Hash Set 대신 Hash Map을 사용해서 접근하였다.

import java.util.*;

public class Baekjoon_10816 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<Integer, Integer> countMap = new HashMap<>();
        StringBuilder result = new StringBuilder();

        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int input = sc.nextInt(); // 상근이의 카드 입력
            if (!countMap.containsKey(input)) {
            	// Map에 없으면 입력값을 key로 가지는 value(갯수)를 1로 저장
                countMap.put(input, 1); 
            }
            else {
            	// 이미 해당 값이 들어있다면 value(갯수)를 1증가
                countMap.replace(input, countMap.get(input) + 1);
            }
        }

        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int input = sc.nextInt(); // 갯수를 셀 정수 입력
            if (countMap.containsKey(input)) {
            	// 입력된 정수가 Map에 존재한다면
                // 해당 정수를 key값으로 가지는 value(개수) 반환
                result.append(Integer.toString(countMap.get(input)) + " ");
            }
            else {
            	// 입력된 정수가 Map에 존재하지 않는다면
                result.append("0 ");
            }
        }
        
        System.out.println(result.toString().trim());

        sc.close();
    }
}

Map에 key와 value를 어떻게 설정해서 저장해야 갯수를 count할 때, 가장 효율적으로 동작할 수 있을 지에 대해 먼저 생각했다.

처음에는 상근이의 카드 정보를 그대로 Map에 저장시켜 구현을 하려 했었는데, 어떻게 하든 원하는 정수를 Map에서 찾을 때 Map 전체를 순회하게 되어 시간 복잡도가 최악의 경우 $O(N^2)$까지 나올 거 같았다.

그래서 좀 더 효율적인 방법을 찾아냈다.
바로, 상근이의 카드를 입력 받을 때, Map에 해당 입력값에 대한 갯수를 미리 다 저장시켜 놓는 방법이다.

입력한 카드의 숫자를 key값, 같은 숫자의 카드 갯수를 value값으로 가지는 Map을 앞에서 만들어 놓으면, 뒤에서 따로 갯수를 일일이 세지 않아도 된다.

이를 구현하기 위해, 상근이의 카드를 쭉 입력받을 때,
Map에 해당 숫자의 카드가 없으면, value(갯수)를 1로 지정해서 저장해주고,
해당 숫자의 카드가 이미 있으면, 해당 숫자를 key값으로 가지는 value(갯수)에 1을 더하도록 해주었다.

이 과정이 완료되면, 상근이가 가지고 있는 카드의 숫자를 key, 해당 숫자의 카드 갯수를 value로 가지는 Map이 완성된다.

문제의 예제 입력을 예로 들면 아래와 같은 결과가 나온다.

이제 주어진 정수들이 상근이의 카드와 일치하는 것이 있는 지, 있다면 갯수를 출력해야 한다.

이미 카드마다의 갯수를 다 구해놓았기 때문에, Map에 포함되는 숫자는 해당 value를 출력해주면 되고, 없으면 0을 출력해주면 최종적으로 문제를 해결할 수 있다.

개선점

조금 더 간결하고 효율적으로 코드를 개선하기 위해 방법을 찾아보았다.

우선 getOrDefault()메서드를 통해, 조건문을 간단하게 표현할 수 있다.

for (int i = 0; i < N; i++) {
	int input = sc.nextInt();
    countMap.put(input, countMap.getOrDefault(input, 0) + 1);
}

상근이의 카드를 입력받을 때 value인자에 getOrDefault()메서드를 사용하게 되면, key가 존재하지 않을 경우 기본값인 0을 반환하고, 존재한다면 해당 input을 key갑으로 가지는 value를 반환해주기 때문에, 조건문을 따로 사용하지 않아도 된다.

for (int i = 0; i < M; i++) {
	int input = sc.nextInt();
    result.append(countMap.getOrDefault(input, 0)).append(" ");
}

결과를 출력할 때도 마찬가지로 getOrDefault()를 사용해 주면, 조건문을 사용하지 않고도 구현할 수 있다.

---

🔗문제 링크
💻Repository