백준 2776 암기왕

·2022년 8월 7일
0

문제

문제 설명

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


Python

from sys import stdin

def binary(array, x, start, end):
    result=0

    while start < end:
        mid = (start + end) // 2
        if array[mid] == x:
            result = 1
            break
        elif array[mid] > x:
            end = mid
        else:
            start = mid + 1

    print(result)


t=int(stdin.readline().strip())
for _ in range(t):
    n = int(stdin.readline().strip())
    a= sorted([i for i in map(int, stdin.readline().strip().split())])
    m = int(stdin.readline().strip())
    b= [i for i in map(int, stdin.readline().strip().split())]

    for i in b:
        binary(a, i, 0, n)

Java

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));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            int n=Integer.parseInt(br.readLine());
            
            int[] a=new int[n];
            
            StringTokenizer st=new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++)
                a[i]=Integer.parseInt(st.nextToken());
            Arrays.sort(a);

            int m=Integer.parseInt(br.readLine());
            
            int[] b=new int[m];
            
            st=new StringTokenizer(br.readLine());
            for(int i=0; i<m; i++)
                b[i]=Integer.parseInt(st.nextToken());

            for(int i:b){
                int start=0;
                int end=n;
                int result=0;

                while(start<end){
                    int mid=(start+end)/2;

                    if(a[mid]==i){
                        result=1;
                        break;
                    }
                    else if(a[mid]>i)
                        end=mid;
                    else
                        start=mid+1;
                }

                bw.write(result+"\n");
            }
        }

        bw.flush();
    }
}

해결 과정

  1. 문제를 보자마자 수첩1의 배열을 Set으로 저장해서 수첩2의 내용이 존재하는지 확인하면 입력 받는 O(n) 시간으로 끝날 것이라고 생각했다. 하지만 Binary Search로 풀어도 각 수첩의 입력 크기는 최대 100만이므로 한 수첩을 정렬하는 데 O(n*log n), 그리고 다른 수첩의 각 요소를 돌면서 Binary Search하면 O(n*log n)이 걸리므로 아무리 커도 1억번 미만의 연산이다.

  2. SetBinary Search 둘다 구현해봤을 때 파이썬 기준으로 4~5배 가량 시간 차이가 났다.

  3. 😁

profile
渽晛

0개의 댓글