문제

문제 풀이

[1차 풀이] - 시간 초과

처음으로 풀었을 때는 일단 결과를 출력해내는 것만 생각해서 시간 초과를 고려하지 못했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 비교할 그룹 - A
        String[] groupA = new String[n];
        groupA = br.readLine().split(" ");
        
        // contains를 사용하기 위해서 List로 변환
        List listA = Arrays.stream(groupA).collect(Collectors.toList());

        int m = Integer.parseInt(br.readLine());
        // 확인할 그룹 - B
        String[] groupB = new String[m];
        groupB = br.readLine().split(" ");

        for(String x: groupB){
            if(listA.contains(x)){
                System.out.println("1");
            }
            else{
                System.out.println("0");
            }
        }
    }
}

---

[2차 풀이] - 참고한 블로그
문제의 의도에 맞게 이진 탐색으로 풀었다.

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

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

        groupA = new int[n];
        for(int i=0;i<n;i++){
            groupA[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] groupB = new int[m];
        for(int i=0;i<m;i++){
            groupB[i] = Integer.parseInt(st.nextToken());
        }

        // 이진 탐색
        // A 배열 정렬
        Arrays.sort(groupA);

        for(int i=0;i<m;i++){
            if(binarySearch(groupB[i]) >= 0){
                System.out.println("1");
            }
            else{
                System.out.println("0");
            }
        }

    }

    // 일치하는 index 값 return
    public static int binarySearch(int x){
        int l = 0;
        int r = n-1;

        while(l <= r){
            int mid = (l + r) / 2;
            if(groupA[mid] == x){
                return mid;
            } else if (groupA[mid] > x) { // 왼편에 x 값이 존재
                r = mid -1;
            }
            else {
                l = mid +1;
            }
        }
        return -1;
    }
}

---

궁금한 점

• 어떤 경우에 이진 탐색을 써야할까?
• 첫번째 방법으로 푸는 경우에는 얼마나 시간 초과가 발생할까?
• 1초라는 시간 제한에서 역으로 이분 탐색을 유추해내는 것은 어떻게 해야할까?
• 메모리 제한은 어떻게 계산해야할까? 128MB는 배열을 몇 개 정도만 써야할까?