[TIL-25/01/14] 99클럽 코테 스터디 1일차 - 백준 2776: 암기왕 - JAVA

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

문제 (실버4)

시간 제한: 2초
메모리 제한 : 256MB

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

 

접근 방식

이 문제는 주어진 입력과 두 개를 비교하여 일치하는 값이 있는지 여부를 확인하는 문제이다. 당연히 두 입력값을 `Array`의 담아 모든 경우를 확인하는 경우 즉, 이중 `for`문 형태는 시간복잡도 `O(n^2)`이므로 올바른 방식이 아니다. 

 

그래서 생각한게 `HashMap`을 이용한 방법이다. 연종이의 값을 `map`에 넣고 그 다음 동규값을 이용해 `map.containsKey`메서드로 연종의 `map`에 값이 있는지 없는지 여부로 찾는 것이다. 

 

 `Map`에서 `contanins`을 하는것은 `List`보다 빠른 시간복잡도인 `O(1)`이므로 이런 탐색문제에는 이점이 있다.

 

풀이 코드 

package backjoon.silver.lv4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class B2776 {

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

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            Map<Integer, Integer> countMap = new HashMap<>();

            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(st.nextToken());
                countMap.put(x, countMap.getOrDefault(x, 0) + 1);
            }

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

            for (int j = 0; j < M; j++) {
                int x = Integer.parseInt(st1.nextToken());
                if (countMap.containsKey(x)) {
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}

 

올바른 접근법

후에 다른 사람의 코드를 확인하고 문제의 힌트를 찾아보니 이 문제는 두 가지 방법으로 풀 수 있는 문제이다. 

1. 해시셋을 이용한 풀이
   1. 첫 번째 수첩의 숫자들을 set에 저장
   2. 두 번째 수첩의 숫자들을 하나씩 확인하며 set에 존재하는지 확인
2. 이분 탐색 풀이
   1. 첫 번째 수첩의 숫자들을 정렬
   2. 두 번째 수첩의 숫자들을 하나씩 이분 탐색으로 확인

 

1. 해시셋을 이용한 풀이

`HashMap`으로 풀어보면 알겠지만 `key-value` 중 하나만 사용하는 것을 알 수 있다. 그렇기 때문에 이 문제는 `HashSet`형태가 더 적합하다. 

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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine()); // 첫 번째 수첩 크기
            StringTokenizer st = new StringTokenizer(br.readLine());
            Set<Integer> note1 = new HashSet<>();

            // 첫 번째 수첩 숫자 저장
            for (int i = 0; i < N; i++) {
                note1.add(Integer.parseInt(st.nextToken()));
            }

            int M = Integer.parseInt(br.readLine()); // 두 번째 수첩 크기
            st = new StringTokenizer(br.readLine());

            // 두 번째 수첩 숫자 확인
            for (int i = 0; i < M; i++) {
                int num = Integer.parseInt(st.nextToken());
                if (note1.contains(num)) {
                    sb.append("1\n");
                } else {
                    sb.append("0\n");
                }
            }
        }
        System.out.print(sb);
    }
}

 

2. 이분탐색을 이용한 방법

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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine()); // 첫 번째 수첩 크기
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] note1 = new int[N];

            // 첫 번째 수첩 숫자 저장
            for (int i = 0; i < N; i++) {
                note1[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(note1); // 정렬

            int M = Integer.parseInt(br.readLine()); // 두 번째 수첩 크기
            st = new StringTokenizer(br.readLine());

            // 두 번째 수첩 숫자 확인
            for (int i = 0; i < M; i++) {
                int num = Integer.parseInt(st.nextToken());
                if (binarySearch(note1, num)) {
                    sb.append("1\n");
                } else {
                    sb.append("0\n");
                }
            }
        }
        System.out.print(sb);
    }

    // 이분 탐색 메서드
    private static boolean binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}