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

pk920207 3년 전 0

이분탐색으로 풀었는데도 시간초과가 계속 발생하네요..

16프로로 한번 올라가고 좀있다가 바로 시간초과 뜨네요.

입력부분에 stream 쓴것은 그렇게 큰 영향을 미칠 것 같지는 않고..

혹시 어떤 부분에서 시간 초과가 발생할까요?

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

public class 암기왕 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        암기왕 fn = new 암기왕();
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            int note1Count = Integer.parseInt(br.readLine());
            int[] note1 = Arrays.stream(br.readLine().split(" ", note1Count))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            Arrays.sort(note1);

            int note2Count = Integer.parseInt(br.readLine());
            int[] note2 = Arrays.stream(br.readLine().split(" ", note2Count))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            Arrays.stream(fn.solution(note1, note2)).forEach(System.out::println);
        }
    }

    public int[] solution(int[] note1, int[] note2) {
        int[] answer = new int[note2.length];

        int low = 0;
        int high = note1.length - 1;
        int mid;

        for (int i = 0; i < note2.length; i++) {
            while(low <= high) {
                mid = (low + high) / 2;

                if(note2[i] == note1[mid]) {
                    answer[i] = 1;
                    break;
                }

                if(note2[i] < note1[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            low = 0;
            high = note1.length - 1;
        }

        return answer;
    }
}

gdsfav 2년 전 0

Arrays.stream(br.readLine().split(" ", note1Count))

.mapToInt(Integer::parseInt)

.toArray();

이 입력부분을 Integer.parseInt(st.nextToken()) 같은 형식으로 봐꿔보는건 어떠신가요?

다른 문제긴 한데, 달빛여우 풀때 입력을 저렇게 받았더니 시간초과나더라구요

Integer.parseInt(st.nextToken()) 로 바꿨더니 바로 통과했구요~

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

문제

문제

출처

ICPC

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

pk920207 3년 전 0

gdsfav 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말