글 읽기 - [Java] 시간초과가 이해가지 않습니다(팰린드롬 문제)

toti010 1년 전 0

문제 10942번입니다. 시간복잡도 O(n)인데 왜 틀릴까요...?

import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int length, questions;

        length = sc.nextInt();
        int[] arr = new int[length];
        for(int i = 0;i<length;i++){
            arr[i] = sc.nextInt();
        }

        questions = sc.nextInt();
        int[][] qarr = new int[questions][2];
        for(int i=0;i<questions;i++)
            for(int j = 0;j<2;j++)
                qarr[i][j] = sc.nextInt()-1;

        problemSolver(arr, qarr);
    }

    static int isPalindrome(int[] arr, int start, int end){
        if(start == end) return 1;
        for(int i = 0;i<=(end-start)/2;i++){
            if(arr[start+i]!=arr[end-i]) return 0;
        }
        return 1;
    }

    static void problemSolver(int[]arr, int qarr[][]){
        int start=0, end=0;
        for(int[] idx : qarr){
            start = idx[0];
            end = idx[1];
            System.out.println(isPalindrome(arr, start, end));
        }
    }
}

5undays 1년 전 0

BufferedReader 사용해보세요. 그리구 알고리즘이 O(n) 는 아닌 것 같은데... 더 줄여보세요

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

문제

문제

출처

ICPC

[Java] 시간초과가 이해가지 않습니다(팰린드롬 문제)

toti010 1년 전 0

5undays 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말