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

풀이 방법

멍청한 풀이

오늘 풀어본 문제는 어제 풀었던 문제의 두번째 시리즈라고 할 수 있습니다. 즉, 숫자카드2 입니다. 어제 숫자카드 문제를 풀면서 이해를 했다고 생각하고 바로 두번째 시리즈에 도전했습니다. 하지만 역시나 시즌2는 쉽지는 않다는 것을 깨달았습니다. 단순하게 Set을 쓰려고했지만, 문제를 읽어보니 Set이 아닌 다른 자료구조를 써야한다는 생각을 했고, 저는 늘 써오던 List를 이용해서 문제를 풀려고 했습니다.

하지만 List를 사용하게 되면 시간초과의 난관을 극복할 수 없었습니다. 애초에 List로 풀어야지라고 마음을 먹으면서 시간초과 날 것 같다는 염려를 했습니다…ㅜㅜ 아직 시간 초과를 해결하기 위한 다른 자료구조를 생각하는 능력이 많이 부족합니다…ㅜㅜ

그래서 일단은 부딪혀보자는 마음으로 List를 사용하여 문제를 풀었습니다. 아래의 코드는 List를 이용한 문제 풀이 방법입니다. 완성된 코드는 아니며 제가 생각해보면서 짠 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ10816 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());

        List<Integer> list = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<N;i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(bf.readLine());
        StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        int[] counts = new int[M];
        int count = 0;
        for(int j=0;j<M;j++){
            int value = Integer.parseInt(st2.nextToken());

            for(int k=0;k<N;k++){
                if(list.get(k).equals(value)){
                    count+=1;
                    counts[M] = count;
                }else {
                    counts[M] = 0;
                }
                sb.append(counts[M]+" ");
                count = 0;

            }
          /*  if(list.contains(value)){
                System.out.println("들어오긴 하니;??"+", "+(j));
                count+=1;
                counts[M] = count;
                System.out.println(counts[M]);
            }else {
                counts[M] = 0;
            }
            sb.append(counts[M]+" ");
            count = 0;*/
        }

        System.out.println(sb.toString());

    }
}

전체적인 틀을 잡았고 어떻게 푸는지 알았지만 List만을 사용해서는 중복된 값이 들어있는 것을 Check하고 갯수를 확인하는 과정이 어려웠습니다. 그래서 생각을 하다가 구글링을 해보았습니다.

생각하고 나서 깨달은 풀이

Map이라는 자료구조를 사용했습니다. Map은 키와 값을 쌍으로 저장하는 자료구조입니다. 특징은 저장 요소의 순서를 유지하지 않고, Key는 중복을 허용하지 않지만, 값은 중복을 허용합니다.

Map을 이용해서 Key, Value 쌍으로 데이터를 저장하는 방식을 사용했습니다. 처음에 상근이가 가지고 있는 카드를 입력받는데, 이 값들을 모두 Map에 저장합니다. 여기서 상근이가 가지고 있는 카드를 Key값으로 정했습니다.

Map은 초기화되지 않은 상태이기 때문에 처음에 들어오는 카드 입력들은 모두 카드를 Key값으로 가지면서 Value는 모두 1을 저장했습니다. 그러다가 앞에서 저장되었던 Key의 카드 입력이 들어오게 되면 기존에 있던 key에 해당하는 value를 1을 더한 값으로 교체해줍니다. *이러한 과정을 거쳐 상근이가 가지고 있는 카드를 입력받으면 Map이라는 자료구조에 상근이가 가지고 있는 카드의 갯수가 저장됩니다.

그리고 추후에 입력받는 카드들을 상근이가 가지고 있는지 비교하는 것이므로 입력받은 카드를 Map의 containsKey() 메소드를 이용해서 카드를 가지고 있는지 비교해서 가지고 있다면 입력받은 카드의 값을 Key로 해서 Map에서 뽑아내어 출력합니다.

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

public class BOJ10816 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken());


            // get()은 key에 해당하는 value를 반환
            if (map.containsKey(key)) {
                map.replace(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }

        int M = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int value = Integer.parseInt(st.nextToken());
            if (map.containsKey(value)) {
                sb.append(map.get(value) + " ");
            } else {
                sb.append(0 + " ");
            }
        }
        System.out.println(sb.toString());
    }
}
// 입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10


// 출력
3 0 0 1 2 0 0 2

배운점

알고리즘을 풀 때 시간초과를 생각하는 방법을 배웠습니다. 이전에는 무작정 풀고 나서 '왜 안되는거지???'라는 생각을 하고 구글링을 해서 다른 방법을 찾아보았다면 이제는 '시간 초과가 나서 안되네…'라는 생각을 하고 시간 초과가 나지 않는 자료구조를 생각해보고 로직을 생각하는 힘을 키우게 된 것 같습니다.

또한, 알고리즘을 풀 때 어떠한 자료구조를 사용해야 할 지 결정하는 능력은 문제를 많이 풀어봐야 한다는 것을 알게 되었습니다. 문제를 보고 도전할 수 있는 자료구조는 List, Set 정도입니다. Map은 무엇인지 알긴 하지만, 알고리즘을 풀 때 어떻게 어떤 상황에서 사용하는지에 대해 잘 모르고 있었기 때문에 부족함을 많이 느꼈습니다. 앞으로 Map을 자주 사용해보고 많이 풀어보도록 노력하는게 좋을 것 같습니다.

[10816]

풀이 방법

VictoryWoo