[백준 | Java] 2776번 암기왕 - BufferedWriter, BufferedReader, StringTokenizer, Map

2675번 / 문자열 반복

❓ 암기왕

🏷️ 관련 주제 : BufferedReader BufferedWriter StringTokenizer Map

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다.
하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다.
동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다.
그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다.
질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다.
연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다.
집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다.
동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다.
다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다.
그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다.
그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고,
다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다.
모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 1

1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

출처

잘못된 데이터를 찾은 사람: august14, djm03178
문제의 오타를 찾은 사람: chjiiwon30

알고리즘 분류

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

---

💦 나의 시도

💥 클래스명은 Main으로 해주세요.

첫 제출에서부터 런타임 에러가 계속 났는데  
제출 기록에서 런타임 에러 글자만 보고 괄호 안에 구체적인 에러 내용이 있는 것을 제대로 확인하지 못해서
무엇때문에 에러가 나는지 발견하지 못해 문제를 푸는데 시간이 한참 걸렸다.  
한참 고민하다 결국 질문 게시판을 이용해서 힌트를 얻으려 했지만
다들 처음 문제 푸는 사람들은 아니니 클래스명을 잘못 작성하여 에러 나는 경우를 찾지 못해 한참 고민하다 
우연히 클래스명을 Main으로 작성해야 한다는 것을 발견할 수 있었다.

Try01. Scanner 클래스와 Map 객체 사용

• nextInt() 메서드로 T, N, M의 입력값을 받음
• 입력 받은 범위(0 ~ T(or N or M) - 1)에서 반복문을 돌며 nextInt() 메서드로 공백으로 구분된 정수값을 받음.
• '수첩 1'에 있는 입력받은 숫자를 키로, 값을 1로 하여 Map에 담음.
  • 입력 받은 값을 체크하기 위해 조회할 때,
    시간복잡도가 O(1)인 Map을 사용하는 것이 적합하다고 판단
• '수첩 2'에 있는 값을 입력 받으며 Map에서 getOrDefault(sc.nextInt(), 0); 메서드 실행하여 그 결과를 출력

예전에 알기로는 입력값의 줄바꿈 부분은 sc.nextLine();으로 공백을 받은 후에 다음 입력값을 받아야 
내가 원하는 값을 제대로 받을 수 있다고 알고 있었는데 
VSCode에서 작성한 코드에서 sc.nextLine();을 사용하지 않았는데도 출력이 제대로 나와서 
내가 알고 있던게 잘못되었나? 그냥 sc.nextLine();을 안 써도 되나? 
헷갈려서 백준 코드에 sc.nextLine(); 없이 코드를 작성해 보았더니 런타임 에러(NumberFormat)가 발생했다.

💥 앞에서 sc.next();나 sc.nextInt();로 입력값을 받고 줄바꿈 후, 다른 값을 입력받을 때는 sc.nextLine();으로 공백을 받아 준 후, 이어서 입력값을 받아주세요.

Try02. 런타임 에러(NoSuchElement)가 왜 발생한 지 바로 파악이 안되어서 Map을 int[]로 바꾸어 봄.

(오늘 본 숫자) - 1을 인덱스로 하는 배열의 원소를 1로 변경한 후, '수첩 2'에 있는 숫자들을 하나씩 체크하려고 함.

💥런타임 에러(ArrayIndexOutOfBounds) 발생

int 배열의 길이를 1,000,000라고 코드를 작성하였다.
그런데 질문의 개수 범위가 1 ≤ N ≤ 1,000,000 라고 했고
오늘 본 정수의 범위는 int라고 하였으므로
배열의 길이는 모든 int형 정수 범위를 체크하려면 int의 값 범위를 길이로 하였어야 했다.

Try03. 입력값을 BufferedReader, StringTokenizer를 이용해서 공백으로 구분된 문자열 입력 받기

• 입력값 받기
  • 객체 생성 : BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  • T, N, M 입력 받기 : int T = Integer.parseInt(br.readLine());
• 수첩의 숫자 입력 받기
  • 객체 생성 : StringTokenizer st = new StringTokenizer(br.readLine());
  • 각 숫자 꺼내기 : st.nextToken();

💥int[] 대신 Map을 사용했지만 시간 초과 발생!

정확히 원인을 찾지는 못해서 출력 시간도 줄여보기로 함.

Try04. BufferedWriter를 사용하여 결과값을 출력

• 객체 생성 : BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
• 문자열 추가 : bw.write();
• 줄바꿈: bw.newLine();
• 문자열 출력 : bw.flush();
• 반복문을 통해 '수첩 2'의 정수를 입력 받을 때, 문자열 추가 및 출력

💥System.out.println(); 대신 BufferedWriter을 사용했지만 시간 초과 발생!

마음 속으로는 Map이 더 빠를 것 같다고 생각했지만  
아까 포기했던 int[]를 다시 사용해 보기로 함.

Try05. 길이 2,147,483,647인 int배열 생성, 입력 받은 수첩 원의 (숫자) - 1을 인덱스로 하는 원소의 값을 1로 변경

💥Map 대신 int[2147483647]을 사용한 결과 메모리 초과 발생!

다시 Map을 사용하기로 함.

Try06. Map에 '수첩 1'의 숫자들을 넣는 과정과 '수첩 2'의 숫자를 확인하는 과정을 함께 진행

• BufferedReader와 StringTokenizer 객체로 '수첩 1'의 숫자를 모두 읽어 옴.
• 바로 수첩 1의 숫자 각각을 Map에 추가하지 않고
  BufferedReader와 StringTokenizer 객체로 '수첩 1'의 숫자를 모두 읽어 옴.
• nextToken() 메서드로 '수첩 2'의 숫자 m 가져오기
• 조건문으로 '수첩 2'의 숫자 체크 결과 구해서 BufferedWriter 객체로 출력하기
  • Map 객체 note1이 m을 키로 포함하면 "1\n" 출력(flush();) 및 반복문 `continue;
  • '수첩 2'의 숫자가 Map의 키에 존재하지 않고 StringTokenizer 객체의 hasMoreTokens() 결과가 true이면 m이 나오거나 다음 Token이 존재하지 않을 때까지 nextToken() 메서드 실행 및 Map에 추가
  • m이 나오면 "1\n" 출력(flush();)
  • 그렇지 않으면 "0\n" 출력(flush();)

💥시간 초과 발생

Try07. BufferedWriter 객체에 문자열 추가만 하고 출력은 맨 나중에 하기

🎉드디어 성공!🎉

• 메모리 : 445640KB
• 시간 : 2072ms

 

📑제출 기록 및 오답 원인

💯 해결 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int T = Integer.parseInt(br.readLine());

            for (int t = 0; t < T; t++) {
                int N = Integer.parseInt(br.readLine());
                StringTokenizer st1 = new StringTokenizer(br.readLine());

                Map<String, String> note1 = new HashMap<>();

                int M = Integer.parseInt(br.readLine());
                StringTokenizer st2 = new StringTokenizer(br.readLine());

                for (int i = 0; i < M; i++) {
                    String m = st2.nextToken();
                    if (note1.containsKey(m)) {
                        bw.write("1\n");
                        continue;
                    }

                    while (st1.hasMoreTokens()) {
                        String n = st1.nextToken();
                        note1.put(n, "1");

                        if (m.equals(n)) {
                            bw.write("1\n");
                            break;
                        }
                    }

                    if (!note1.containsKey(m)) {
                        bw.write("0\n");
                    }
                }
            }

            bw.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

🏷️ 문제 풀면서 참고한 블로그

[Java] 코테 준비를 위한 입출력