[Algorithm] 99클럽 코테 스터디 1일차 TIL BOJ 2776

문제

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

풀이

이미 입력값을 받는 과정에서 for문을 사용하고 있기 때문에 결과를 출력하는 과정에서 시간을 최대한 줄여야겠다고 생각했고 HashMap을 사용해야겠다고 느꼈다.

수첩1의 값을 map에 저장하고 그에 대한 value를 1로 설정한다
그리고 수첩2에 대한 값들을 입력받는 시점에 map에 그 숫자가 존재하는지 확인한다
존재하지 않을 경우에는 0을 반환하도록 한다

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

        int TC = Integer.parseInt(br.readLine());
        HashMap<String, Integer> note1 = new HashMap<>();

        for (int i=0; i<TC ; i++) {
            int note1Size = Integer.parseInt(br.readLine());
            String[] token1 = br.readLine().split(" ");
            for (int j = 0; j < note1Size; j++) {
                note1.put(token1[j], 1);
            }

            int note2Size = Integer.parseInt(br.readLine());
            String[] token2 = br.readLine().split(" ");
            for (int j = 0; j < note2Size; j++) {
                int result= note1.getOrDefault(token2[j], 0);
                bw.write(result+"\n");
            }

            note1.clear();
        }
        bw.flush();
        bw.close();
    }
}

TIL

문제를 풀이하며 처음에는 시간초과로 통과에 실패했다.
그러나 HashMap을 사용했는데 이보다 더 시간복잡도가 작을 수 있을까? 라는 생각이 들었다.
그래서 입출력 함수를 수정하기로 했다.

예전에도 알고리즘을 풀 때 입력에서 Scanner를 사용해서 시간초과가 났던 경험이 있어 BufferedReader를 사용할 수 있도록 연습을 했었다.
그러나 출력에는 항상 System.out.println을 사용했었는데 시간초과를 본 이후에 BufferedWriter를 사용하는 방법으로 수정해보았더니 문제를 통과할 수 있었다.

BufferedWriter의 사용법은 다음과 같다
또한 System.out.println처럼 개행을 자동으로 넣어주지 않기 때문에 개행이 필요하면 \n 을 사용하여 직접 개행을 넣어주어야 한다

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   //할당된 버퍼에 값 넣기
String s = "hello!";   //출력할 문자열
bw.write(s);   //버퍼에 있는 값 전부 출력
bw.flush();   //남아있는 데이터를 모두 출력시킴
bw.close();   //스트림을 닫음