[백준/Java] #10816 숫자 카드 2 - 시간초과 문제 해결

 

 

문제

 

 

 

 

 

코드

 

처음 시도했을 때 시간 초과로 실패했다.

import java.io.*;
import java.util.stream.Stream;

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));

        int n = Integer.valueOf(br.readLine());
        int[] nums = getNums(n, br);

        int m = Integer.valueOf(br.readLine());
        int[] counts = getNums(m, br);

        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (counts[i] == nums[j]) count++;
            }
            bw.write(count + " ");
        }
        bw.close();
    }

    static int[] getNums(int n, BufferedReader br) throws IOException {

        String[] split = br.readLine().split(" ");
        return Stream.of(split)
                .mapToInt(Integer::valueOf)
                .toArray();
    }
}

 

위와 같이 작성했었는데, 전체 배열을 돌면서 조건에 맞는 값을 찾는 부분에서 시간이 오래 걸리게 된 것 같다.

그래서 HashMap을 사용하는 방법으로 변경하였다.

 

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

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));

        HashMap<Integer, Integer> map = new HashMap<>();

        int n = Integer.valueOf(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) {
            int key = Integer.valueOf(st.nextToken()); //입력받은 값을 key로 설정하여
            map.put(key, map.getOrDefault(key, 0) + 1); //map에 넣음(디폴트 0, key의 값에 +1)
        }

        int m = Integer.valueOf(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < m; i++) {
            int key = Integer.valueOf(st.nextToken()); //입력받은 값을 key로 설정하여
            int count = map.getOrDefault(key, 0); //해당 key의 값을 꺼냄

            bw.write(count + " ");
        }
        bw.close();
    }
}

 

 

BufferedWriter로 출력하는 것과 StringBuilder + System.out.print를 이용하는 것의 시간 차가 궁금해서 둘 다 해봤는데, 거의 차이가 나지 않았다.

 

 

위: StringBuilder + System.out.print 사용

아래: BufferedWriter 사용