[BOJ] 2776. 암기왕 (java)

✏️ 문제

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

 

🔢 알고리즘

 

#자료구조  #해시

 

 

🤯 풀이 방법

 

먼저 일단 배열에 다 집어넣고 입력 받는 숫자마다 존재 여부를 출력했더니 시간 초과가 났다

대신 더 빠르게 찾을 수 있는 HashMap으로 적용했는데도 시간초과가 나서,

매번 System.out.println으로 출력하는 대신 BufferedWriter를 적용해서 출력 속도를 빠르게 했다.

 

 

👾 구현 코드 (자바)

 시간 초과 코드 (ArrayList + System.out.println 사용) 🔽

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

public class Main {
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      int tc = Integer.parseInt(st.nextToken());  // 테스트 케이스의 수
      
      for (int t = 0; t < tc; t++) {  // 테스트 케이스 수만큼 반복
        st = new StringTokenizer(br.readLine());
        int N1 = Integer.parseInt(st.nextToken()); // 숫자 개수
        
        st = new StringTokenizer(br.readLine());
        List<Integer> l = new ArrayList<>();
        
        while (st.hasMoreTokens()) {
            l.add(Integer.parseInt(st.nextToken()));
        }
        
        st = new StringTokenizer(br.readLine());
        int N2 = Integer.parseInt(st.nextToken()); // 숫자 개수
        
        st = new StringTokenizer(br.readLine());  // 적어 둔 숫자 입력
        while (st.hasMoreTokens()) {
            Integer cur = Integer.parseInt(st.nextToken());  // 숫자 하나씩 확인
            if (l.contains(cur)) {
              System.out.println(1);
            } else {
              System.out.println(0);
            }
        }
        
      }
  }
}

 

 

 제출 코드 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int tc = Integer.parseInt(st.nextToken());  // 테스트 케이스의 수
		
        // BufferedWriter 하나에 저장
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int t = 0; t < tc; t++) {  // 테스트 케이스 수만큼 반복
            st = new StringTokenizer(br.readLine());
            int N1 = Integer.parseInt(st.nextToken()); // 숫자 개수

            st = new StringTokenizer(br.readLine());
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

            while (st.hasMoreTokens()) {
                Integer cur = Integer.parseInt(st.nextToken());  // 숫자 하나씩 입력
                map.put(cur, 1);
            }

            st = new StringTokenizer(br.readLine());
            int N2 = Integer.parseInt(st.nextToken()); // 숫자 개수

            st = new StringTokenizer(br.readLine());  // 적어 둔 숫자 입력
            while (st.hasMoreTokens()) {
                Integer cur = Integer.parseInt(st.nextToken());  // 숫자 하나씩 확인

                if (map.containsKey(cur)) {
                    bw.write("1");
                } else {
                    bw.write("0");
                }

                // 마지막 토큰이 아니라면 개행 문자 추가
                if (st.hasMoreTokens()) {
                    bw.write("\n");
                }
            }
            if (t != tc - 1) {
                bw.write("\n");
            }
        }
		
        // 마지막에 한 번에 출력
        bw.flush();
        bw.close();
    }
}

 

 

🤖 GPT의 제안

• HashMap에서 HashSet으로 변경:
  • map.containsKey(cur) 대신 set.contains(cur)를 사용했습니다. HashSet은 HashMap과 비슷하지만, 값을 저장하지 않고 키만 저장합니다. 이 경우 값이 필요 없으므로 HashSet을 사용하는 것이 더 적합합니다.
  • set.add(cur)는 중복을 자동으로 처리하므로 별도의 값 체크가 필요 없습니다.

HashSet<Integer> set = new HashSet<Integer>();  // HashMap -> HashSet

while (st.hasMoreTokens()) {
    Integer cur = Integer.parseInt(st.nextToken());  // 숫자 하나씩 입력
    set.add(cur);  // HashSet을 사용하여 자동으로 중복을 제거
}

 

• 출력 처리 최적화:
  • BufferedWriter는 여러 번의 출력보다 한 번에 출력하는 것이 효율적입니다.
  • 각 테스트 케이스의 결과를 StringBuilder에 추가한 후, 마지막에 BufferedWriter로 한 번에 출력하도록 변경했습니다.
  • StringBuilder는 문자열을 효율적으로 연결할 수 있는 자료구조입니다. 이를 사용하면 bw.write 호출을 최소화할 수 있습니다.