글 읽기 - JAVA를 이용하여 기수정렬 해서 풀의했는데..

taeguekin 5년 전 0

문제힌트로 카운팅 정렬 또는 기수 정렬을 이용하여 풀이를 하면 된다고 하여서

기수 정렬을 이용해서 해봤는데 12%에서 계속 시간초과가 나는데..

잘못된 부분이나 시간을 더 줄일 수 있는 방법이 있을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class 일공구팔구 {
	
	@SuppressWarnings("unchecked")
	private static Queue[] counter = new Queue[] {
			new LinkedList<Integer>(), new LinkedList<Integer>(),
			new LinkedList<Integer>(), new LinkedList<Integer>(),
			new LinkedList<Integer>(), new LinkedList<Integer>(),
			new LinkedList<Integer>(), new LinkedList<Integer>(),
			new LinkedList<Integer>(), new LinkedList<Integer>()
	};
	
	public static void main(String[] args) throws NumberFormatException, IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		int[] map = new int[t];
		int len = 0;
		for(int i=0;i<t;i++){
			map[i] = Integer.parseInt(br.readLine());
			if(len<map[i]){
				len = map[i];
			}
		}
		
		sortLSD(map, (int)(Math.log10(len)+1));
		
	}
	
	public static void sortLSD(int[] array, int maxdigitSymbols) throws IOException{
		int mod = 10;
		int dev = 1;
		for(int i=0;i<maxdigitSymbols; i++, dev*=10, mod *=10){
			for(int j=0;j<array.length;j++){
				int bucket = (array[j]%mod) / dev;
				counter[bucket].add(array[j]);
			}
			int pos = 0;
			for(int j=0;j<counter.length;j++){
				while(!counter[j].isEmpty()){
					array[pos++] = (int) counter[j].poll();
				}
				
			}
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i : array){
			bw.write(i+"\n");
		}
		bw.flush();
	}
}

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

문제

문제

출처

ICPC

JAVA를 이용하여 기수정렬 해서 풀의했는데..

taeguekin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말