[99클럽 코테 스터디 1일차 TIL / 백준] 2776 - 암기왕 (JAVA)

99클럽 코테스터디 1일차 TIL
KeyWord : HashSet, BinarySearch

문제

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

---

풀이

불과 2주전에 풀이하여 올렸던 문제와 99% 유사한 문제였기에 쉽게 해결했다.

[백준]10815 - 숫자 카드 (JAVA))

이 문제인데, 출력형식과 값의 범위 정도를 제외하면 문제가 똑같다.

위 글과 마찬가지로, 이번에도 HashSet과 BinarySearch 두 가지 방법으로 풀이해보았으며, 입력은 두 풀이 모두 BufferedReader, 출력은 StringBuilder를 이용해 한 번에 모아 출력해주었다.

HashSet

HashSet에 값을 저장한 후, 출력하기만 하면 된다.

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.HashSet;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        HashSet<Integer> memo;  
        StringTokenizer stk;  

        int T = Integer.parseInt(br.readLine());  

        for (int j = 0; j < T; j++) {  
            memo = new HashSet<>();  

            int N = Integer.parseInt(br.readLine());  
            stk = new StringTokenizer(br.readLine());  
            for (int i = 0; i < N; i++) {  
                memo.add(Integer.parseInt(stk.nextToken()));  
            }  

            int m = Integer.parseInt(br.readLine());  
            stk = new StringTokenizer(br.readLine());  
            for (int i = 0; i < m; i++) {  
                sb.append(memo.contains(Integer.parseInt(stk.nextToken())) ? 1 : 0).append('\n');  
            }  
        }  

        System.out.println(sb);  
    }  
}

BinarySearch

이 방법도 매우 간단하다.

1. 배열에 값을 저장
2. 배열을 정렬
3. 이진탐색

HashSet 보다 손이 조금 더 간다는 점 빼고는 어렵지 않게 해결할 수 있다.

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.HashSet;  
import java.util.StringTokenizer;

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        StringTokenizer stk;  
        int[] memo;  

        int T = Integer.parseInt(br.readLine());  
        for (int i = 0; i < T; i++) {  
            int n = Integer.parseInt(br.readLine());  
            memo = new int[n];  
            stk = new StringTokenizer(br.readLine());  
            for (int j = 0; j < n; j++) {  
                memo[j] = Integer.parseInt(stk.nextToken());  
            }  

            Arrays.sort(memo);  

            int m = Integer.parseInt(br.readLine());  
            stk = new StringTokenizer(br.readLine());  
            for (int j = 0; j < m; j++) {  
                if (binarySearch(memo, Integer.parseInt(stk.nextToken()))) {  
                    sb.append(1).append('\n');  
                } else {  
                    sb.append(0).append('\n');  
                }  
            }  
        }  
        System.out.println(sb);  
    }  

    private static boolean binarySearch(int[] memo, int num) {  
        int min = 0;  
        int max = memo.length - 1;  
        while (min <= max) {  
            int mid = (min + max) / 2;

            if(memo[mid] == num) {  
                return true;  
            }  
            if (memo[mid] < num) {  
                min = mid + 1;  
            }  
            if (memo[mid] > num) {  
                max = mid - 1;  
            }  
        }  
        return false;  
    }  
}

리마인드 겸, 연습을 위해 Arrays.binarySearch를 사용하지 않고 직접 구현하여 사용해보았다. 처음에 max와 min 로직을 반대로 적용해서, 10분 정도 시간을 허비했다.

---

HashSet의 탐색 시간 복잡도는 $O(1)$ BinarySearch의 경우에는 $O(log{n})$이다. 실제로 HashSet이 더 빠른 것을 확인할 수 있다. (HashSet은 1436ms, BinarySearch는 1892ms)

여담이지만, 어디가 잘못된 건지 찾아보던 중에 binarySearch를 사용할 때 min에서 오버플로우가 발생할 수 있다는 것을 깨달았다. 이 문제에서는 오버플로우가 발생하지는 않지만, 값이 커지는 경우 발생할 수 있다.

int mid = (min + max) / 2;이 부분을 int mid = (min + (max - min) / 2);로 변경하면 오버플로우를 방지할 수 있다.