[Java] baekjoon_10816 : 숫자 카드 2

자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵

숫자 카드 2 : Silver4

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

10816번: 숫자 카드 2

 

첫 번째 코드 작성

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
public static void main(String[] args) throws IOException {

    int N = Integer.parseInt(br.readLine());
    BigInteger[] cards = new BigInteger[N];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      cards[i] = new BigInteger(st.nextToken());
    }

    int M = Integer.parseInt(br.readLine());
    BigInteger[] numbers = new BigInteger[M];
    int ret[] = new int[M];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < M; i++) {
      numbers[i] = new BigInteger(st.nextToken());
    }

    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        if (cards[j].equals(numbers[i])) {
          ret[i]++;
        }
      }
    }

    for (int i = 0; i < M; i++) {
      bw.write(ret[i] + " ");
    }
    bw.newLine();
    bw.close();
  }
}

 

ㄴ 이중 for 문을 이용하여 코드를 작성했을 때 시간 초과가 발생하는 것을 확인하였다.

 

두 번째 코드 작성

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // 상근이가 가지고 있는 숫자 카드의 개수 N
    int N = Integer.parseInt(br.readLine());

    // 숫자 카드에 적혀있는 정수를 저장하는 HashMap
    HashMap<Integer, Integer> cardMap = new HashMap<>();

    // 숫자 카드에 적혀있는 수 입력
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
        int num = Integer.parseInt(st.nextToken());
        // HashMap에 해당 숫자가 이미 있다면 기존 값을 가져와 1 증가시키고, 없다면 1로 설정
        cardMap.put(num, cardMap.getOrDefault(num, 0) + 1);
    }

    // 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수 개수 M
    int M = Integer.parseInt(br.readLine());

    // 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수를 배열에 저장
    int[] numbersToFind = new int[M];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < M; i++) {
        numbersToFind[i] = Integer.parseInt(st.nextToken());
    }

    // 결과 출력
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < M; i++) {
        // HashMap에서 해당 숫자의 개수를 가져오고, 없다면 0을 출력
        sb.append(cardMap.getOrDefault(numbersToFind[i], 0)).append(" ");
    }

    bw.write(sb.toString());
    bw.newLine();
    bw.close();
  }
}

 

ㄴ 시간 초과를 해결하기 위해 HashMap 을 이용하도록 코드를 수정하였다.

 

 

getOrDefault()

ㄴ Java에서 Map 인터페이스의 메서드 중 하나이다.

ㄴ 주어진 키에 대한 값을 반환하되, 해당 키가 맵에 없을 경우에는 기본값을 반환하는 메서드이다.

 

메서드의 시그너처는 다음과 같다.

V getOrDefault(Object key, V defaultValue)

 

ㄴ 여기서 key는 값을 가져올 키이고, defaultValue는 키가 맵에 없을 때 반환할 기본값이다.

 

위에서 작성한 코드를 예시로 들면,

cardMap.put(num, cardMap.getOrDefault(num, 0) + 1);

ㄴ 해당 코드는 cardMap 이라는 이름의 HashMap에 해당 숫자가 이미 있다면 기존 값을 가져와 1 증가시키고, 없다면 1로 설정하는 부분이다.

 

sb.append(cardMap.getOrDefault(numbersToFind[i], 0)).append(" ");

 

ㄴ 해당 코드는 StringBuilder에 cardMap 이라는 이름의 HashMap에서 해당 숫자의 개수를 가져오고, 없다면 0을 출력하는 부분이다.

 

---

 

 

문제점 : 이중 for문을 이용했을 때 시간 초과가 발생하는 것을 확인했다.

해결 방법 : HashMap을 이용하여 카드 숫자를 key로 설정하고, 카운팅하여 정의하였다. 그 후, 넷째 줄에서 입력되는 숫자가 HashMap에 존재할 경우 해당 숫자의 카운트 값을 StringBuilder에 더하고, 존재하지 않을 경우 0을 StringBuilder에 더하도록 했다.

깨달은 바 : 해결 과정에서 Map 인터페이스의 메서드인 getOrDefault 를 사용하는 방법에 대해 알게되었다.