글 읽기 - [java] 시간초과...

ysd1029 7년 전 0

우선 퀵소트로 시도해보았지만 시간초과가 나서

sort() 메서드를 이용해보았지만 시간초과네요...

어떻게 해야하나요?

ps) Arrays.sort() 는 시간복잡도 몇 정도로 생각하면 될까요?

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++){
            int input = scan.nextInt();
            arr[i] = input;
        }
        Arrays.sort(arr);
        for(int i =0;i<n;i++){
            System.out.println(arr[i]);
        }
    }
}

sksdong1 7년 전 0

데이터가 퀵소트 최악의 경우로 들어와서 n^2뜨는거 같네요

Arrays.sort()도 퀵소트 정도라고 보시면 될 거에요

이 문제는 주어지는 범위가 -1,000,000~1,000,000 이라는 점을 이용해서

인덱스에 값 자체를 저장하는 방식으로 O(n)에 해결가능해요

ysd1029 7년 전 0

인덱스에 값자체를 저장하는 방식이란 게 무슨 말인지 궁금합니다 ㅎㅎ

ArrayList로 해서 Collection.sort(arr) 이런식으로 가는걸 말씀하시는건지..음

그리고.. Collection.sort 는 어느정도의 시간 복잡도일까요?

sksdong1 7년 전 1

문제 조건을 보면 값이 중복되지 않고 범위가 2백만이내이기 때문에

10 50 30 40 5

이런식으로 들어오면 arr[10]=arr[50]=arr[30]=arr[40]=arr[5]=true로 놓고

0부터 true인것만 쫙 출력하면 정렬이 되서 나오겠져

sksdong1 7년 전 0

컬렉션 소트나 어레이 소트나 같겠죠..

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

문제

문제

출처

ICPC

[java] 시간초과...

ysd1029 7년 전 0

sksdong1 7년 전 0

ysd1029 7년 전 0

sksdong1 7년 전 1

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말