글 읽기 - 12%에서 시간 초과가 뜨세요... ㅜㅜ 도와주세요

shfksekdrms2 6년 전 0

12%에서 계속 시간초과뜨네요...

아마 Arrays.sort() 써서 그런건가싶은데...

그럼 여기서 의도하는건

셀렉트 정렬, 삽입 정렬 등의 정렬 방식을 의도하는건가요...?

도와주시면 감사하겠습니다... ㅜㅜ

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

//10989
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int i;
		for (i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		
		for (i = 0; i < n; i++) {
			System.out.println(arr[i]);
		}

	}
}

djm03178 6년 전 1

선택 정렬, 삽입 정렬 등은 평균이 O(N^2)이라 더욱 좋지 않고요, 여기서 써야 하는 방법은 따로 있습니다. 참고로, https://www.acmicpc.net/step/9 에 힌트가 나옵니다.

shfksekdrms2 6년 전 0

djm03178 님 감사합니다. 알려주신 방법이 도움이 많이 됬습니다. 하지만 한가지 질문이 더 있습니다.

기수 정렬과 카운팅 정렬로 하는 방법이 있다고 써있던데 기수 정렬은 아직 해보지는 않았고

카운팅 정렬을 이용하여 정렬을 하였습니다. 그런데 여전히 시간 초과가 발생하는 군요... 이건 왜 그런건지 잘 모르겠습니다...

시간으로 보면 O(n) 시간 밖에 안드는데도 말이죠... 왜그런지 알 수 있을까요?

기수 정렬 방법은 시도후에 댓글 업데이트하겠습니다.

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

//10989
public class Main {
	//카운트 정렬
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int i;
		
		int[] arr = new int[n]; //정렬 전
		int[] sortArr = new int[n]; //정렬
		int[] cnt = new int[n]; //카운트 갯수
		int[] sumCnt = new int[n]; //카운트 갯수 누적
		
		//입력
		for(i=0; i<n; i++){
			arr[i] = Integer.parseInt(br.readLine());
		}
		//갯수 카운트
		for(i=0; i<n; i++){
			cnt[arr[i]-1]++;
		}
		//누적 갯수 카운트
		sumCnt[0] = cnt[0];
		for(i=1; i<n; i++){
			sumCnt[i] = sumCnt[i-1] + cnt[i];
		}
		
		for(i=n-1; i>=0; i--){
			sumCnt[arr[i]-1]--;
			sortArr[sumCnt[arr[i]-1]] = arr[i];
		}
		
		for(i=0; i<n; i++){
			System.out.println(sortArr[i]);
		}
		
	}
}

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

문제

문제

출처

ICPC

12%에서 시간 초과가 뜨세요... ㅜㅜ 도와주세요

shfksekdrms2 6년 전 0

djm03178 6년 전 1

shfksekdrms2 6년 전 0

djm03178 님 감사합니다. 알려주신 방법이 도움이 많이 됬습니다. 하지만 한가지 질문이 더 있습니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말