글 읽기 - 시간초과 나는 이유를 모르겠습니다

noodle9407 1년 전 0

뭐가 문제일까요? 배열을 List로 바꾸는데서 문제가 생기는 걸까요...

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        int[] arr1 = new int[n];

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

        st = new StringTokenizer(br.readLine(), " ");

        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        int[] arr2 = new int[m];

        for(int i=0;i<m;i++){
            arr2[i] = Integer.parseInt(st.nextToken());
        }
        List<Integer> list = Arrays.stream(arr1).boxed().collect(Collectors.toList());

        for(int i=0; i<m; i++){
            if(list.contains(arr2[i]) == true){
                System.out.print(1+" ");
            }else{
                System.out.print(0+" ");
            }
        }


    }

}

seawon0808 1년 전 1

제가 자바를 잘 모르지만 40번째 줄에서 list.contains(arr2[i])는 O(n) 인 것 같습니다.

이 문제는 이분탐색을 사용해서 O(logn) 에 확인해야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 나는 이유를 모르겠습니다

noodle9407 1년 전 0

seawon0808 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말