[Java] 5단계. 숫자 카드 2 [10816번]

항해99를 하면서 풀어봤던 문제지만 다시 한 번 풀어보기

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

• 예제 입력1

10
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

---

• 문제 접근
  • 입력
    • 첫째 줄 : 상근이가 가진 카드 개수 N (1 <= N <= 500,000)
    • 둘째 줄 : 숫자 카드에 적힌 정수 (-10,000,000 <= 숫자 <= 10,000,000)
    • 셋째 줄 : M (1 <= N <= 500,000)
    • 넷째 줄 : 상근이가 몇 개 가지고 있는 숫자 카드인지 비교할 숫자 카드 (-10,000,000 <= 숫자 <= 10,000,000)
  • 출력
    • 네 번째 줄에 있는 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분하여 한 줄 출력
• 문제 해결
  • 숫자 카드 1 문제와 달라진 점은 상근이가 가진 숫자 카드(둘째 줄)이 중복되어 카운팅을 해야하는 것
  • 방법1) 배열을 이용하여 둘째 줄의 숫자가 들어올 때마다 해당 숫자 index 카운트
  • 방법2) Map을 이용하여 디폴트 값을 0으로 잡고, 중복된 Key값(숫자 카드)가 들어오면 Value += 1
• 방법1) 배열 풀이 [메모리 : 196,808 KB / 시간 : 824 ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int N = Integer.parseInt(br.readLine());
    int[] sangCard = new int[20000001];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 1; i <= N; i++){
        int number = Integer.parseInt(st.nextToken());
        sangCard[number + 10000000]++;
    }

    int M = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < M; i++){
        int number = Integer.parseInt(st.nextToken());
        sb.append(sangCard[number + 10000000]).append(" ");
    }

    sb.deleteCharAt(sb.length() - 1);
    System.out.println(sb);
}

• 방법2) HashMap 풀이 [메모리 : 199,276KB / 시간 : 1,136ms]

public static void main(String[] args) throws IOException {
    Map<Integer, Integer> cardMap = new HashMap<>();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int N = Integer.parseInt(br.readLine());
    int[] sangCard = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();
    for(int i = 0; i < N; i++){
        if(cardMap.containsKey(sangCard[i])){
           cardMap.put(sangCard[i], cardMap.get(sangCard[i]) + 1);
        } else {
            cardMap.put(sangCard[i], 1);
        }
    }

    int M = Integer.parseInt(br.readLine());
    int[] compareCard = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();
    for(int i = 0; i < M; i++){
        sb.append(cardMap.getOrDefault(compareCard[i], 0)).append(" ");
    }

    sb.deleteCharAt(sb.length() - 1);
    System.out.println(sb);
}

• Stream 풀이 [메모리 : 184,216 KB / 시간 : 1,032 ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    br.readLine();
    Map<Integer, Integer> cardMap = Arrays.stream(br.readLine().split(" "))
            .map(Integer::parseInt)
            .collect(Collectors.toMap(key -> key, value -> 1, Integer::sum));


    br.readLine();
    Arrays.stream(Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray())
                    .mapToObj(i -> cardMap.getOrDefault(i, 0))
                    .forEach(res -> sb.append(res).append(" "));

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

---

• 배열 풀이는 2,000만개의 공간을 잡아두기 때문에 메모리적으로 성능이 매우 안 좋을 거라 생각하였으나, 의외로 HashMap 풀이보다 3,000 KB 가량 더 적었으며, 속도는 더욱 빨랐음
• 배열변수[인덱스]로 바로 접근하기 때문에 시간 복잡도가 O(1)이기 때문일 것이라 생각이 됨
• stream을 사용하기가 아직 익숙치 않지만 그래도 사용하다보니 점점 감이 잡히고 가독성적인 측면에서 매우 강력하다는 게 느껴짐