백준 88570779 암기왕

문제: 백준 88570779번 암기왕

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩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 5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

풀이

N개의 정수(1 ≤ N ≤ 1,000,000)를 입력받은 후, M개의 정수를 다시 입력받습니다.
입력받은 M이 N에 존재하는지 여부에 따라 순차적으로 1 or 0을 출력합니다.

1차 시도

아주 단순히 생각하여 Array를 생성하여 N개의 정수를 저장하고,
이후 M개의 정수를 받아 반복문을 돌리며 체크 할 생각이었다.

그러나 테스트 케이스 단계에서 한번, M개의 정수 입력에서 한번으로 이미 2중 for문 상태라서
굳이 for문을 사용하기 보다는 HashMap의 map.containsKey or map.containsValue를 사용하거나 HashSet의 set.contains를 사용하는 방향으로 선택했다.

2차 시도

Key-Value를 요하는 알고리즘이 아니었기 때문에 Set을 이용하기로 했다.
Hash Table 을 이용하는 Set으로 탐색시, 시간 복잡도는 평균 O(n)이기 때문에
다중 반복문보다 효율적일거라 판단하였으며, 가독성 역시 이쪽이 나을거라 생각한다.

int qst = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < qst; i++)
                bw.write(set.contains(Integer.parseInt(st.nextToken())) ? "1\n" : "0\n");
                

M(qst)만큼 반복문을 진행하며 미리 저장한 N개의 메모를 저장한 set에 contains로 해당 정수가 포함되어 있는지 판단하여 1 혹은 0을 출력한다.

제출

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

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());
        for (int t = 0; t < tc; t++) {
            int memo = Integer.parseInt(br.readLine());
            HashSet<Integer> set = new HashSet<>(memo);
            
            StringTokenizer st = new StringTokenizer(br.readLine());            
            for (int i = 0; i < memo; i++)
                set.add(Integer.parseInt(st.nextToken()));      
            
            int qst = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < qst; i++)
                bw.write(set.contains(Integer.parseInt(st.nextToken())) ? "1\n" : "0\n");
        }      
		bw.flush();
    }
}

후기

사용한buffer는 코드가 끝날 때 close()를 통하여 닫아줘야 한다.
그러나 백준에서 close()를 사용하면 동작 시간이 늘어나는걸 보고 의도적으로 제거했다.
백준 서버상 JVM의 가비지 콜렉터가 해결해 줄거라고 생각한다.