글 읽기 - JAVA 기수정렬로 풀고있는데 12%에서 계속 시간초과나요..

pts119 6년 전 0

1차원배열로 입력값을 일단 받고 HashMap과 ArrayList을 이용해서 정렬한 결과를 각 단계마다 1차원배열에 넣는 방식으로 풀었습니다.

예를들어 반복문 단계별 디버깅을 하면 HashMap같은경우는 이렇게 나오죠..

{0=[0], 1=[81], 2=[72], 3=[383], 4=[274], 5=[125], 6=[96], 9=[9]}

{0=[0, 9], 2=[125], 7=[72, 274], 8=[81, 383], 9=[96]}

{0=[0, 9, 72, 81, 96], 1=[125], 2=[274], 3=[383]}

쨌든.. 어떤 부분에서 시간을 잡아먹는지 알고 싶은데, 고수님들 도와주세요!!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Main {
	int[] intArr;
	ArrayList<Integer> eachList;
	Map<Integer, ArrayList<Integer>> map;
	public static void main(String[] args) throws IOException{
		new Main();
	}
	Main() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int loop = Integer.parseInt(inputStr);
        intArr = new int[loop];
        map = new HashMap<>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
        // 0. int배열에 입력값 넣기.
        int maxLen = 0;
        for(int i=0; i<loop; i++){
        	String valueStr = br.readLine(); 
        	if(valueStr.length() > maxLen){
        		maxLen = valueStr.length();
        	}
        	intArr[i] = Integer.parseInt(valueStr);
        }
        
        int mod = 1, divide = 1;
        for(int i=0; i<maxLen; i++){	// 입력된 값의 최대자릿수만큼 반복.
    		map.clear();
    		list.clear();
    		mod = mod * 10;
        	if(i==0){
    			divide = 1;
    		}else{
    			divide = divide * 10;
    		}
        	
        	for(int j=0; j<loop; j++){	// 배열 하나씩 훑기.
        		int arrJ = intArr[j]%mod/divide;
        		// 각 자릿수그룹에 데이터 넣기.
        		if(map.get(arrJ) == null){
        			list = new ArrayList<Integer>();
        		}else{
        			list = map.get(arrJ);
        		}
        		list.add(intArr[j]);
        		map.put(arrJ, list);
        	} //end for : 배열 하나씩 훑기.
        	
        	inputToArr();	// map에 들어가며 정렬된 값 배열에 다시 넣기.
        	
        } //end for : 입력된 값의 최대자릿수만큼 반복.
        
        // 출력.
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i : intArr) 
		{
			bw.write(i + "\n");
		}
		bw.flush();
        
	} //end Main
	
	void inputToArr(){
		int cnt=0;
		for(int i : map.keySet()){
			eachList = map.get(i);	// 각 Key가 갖고있는 ArrayList를 끄집어내.
			for(int val : eachList){
				intArr[cnt++] = val;
			}
		}
	} //end inputToArr()
}

chogahui05 6년 전 0

HashMap에서 극단적으로 충돌이 많이 날 때

시간 복잡도가 O(n)이 아니라 O(nlogn)쯤 될 거 같네요.

그런데. 수의 범위가 1부터 10000까지고, 수의 갯수가 1000만까지 간단 말이죠..

최악의 경우에는 중복되는 키의 갯수가 1000만개 가까이 되네요.

물론, O(nlogn) 복잡도로도 충분히 통과는 가능한데요.

기수 정렬의 특성상 앞에 붙는 상수가 많이 크네요.. 5자리 수인 경우에는 5번 버킷에 넣고 빼고 그래야 하니까요.

아예 버킷과 Arraylist로만 퉁칠 수 있을 거 같은데요. 이 부분은 어떻게 생각하세요??

심지어 이건 수의 범위도 작잖아요.

pts119 6년 전 0

조언해 주신대로 HashMap을 없애고 ArrayList[] 배열과 ArrayList로 해봤는데 여전히 12%에서 시간초과가떴었구요,

구글링해서 발견한 대상수와 누적수를 이용한 기수정렬로 풀었습니다 ㅎㅎ 이 방법은 1차원 배열만 써먹어서 속도가 개선된거같네요 후우..

쨌든 조언해주신 방법은 참고용으로 아래 소스에 올립니다.

조언 감사드립니다!!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

/** 기수 정렬(Radix Sort)를 사용 */
public class Main {
	int[] intArr;
	ArrayList<Integer> list;
	ArrayList<Integer>[] radixGrp;
	
	public static void main(String[] args) throws IOException{
		new Main();
	}
	Main() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int loop = Integer.parseInt(inputStr);
        intArr = new int[loop];
        radixGrp = new ArrayList[10]; 
		
        // 0. int배열에 입력값 넣기.
        int maxLen = 0;
        for(int i=0; i<loop; i++){
        	String valueStr = br.readLine(); 
        	if(valueStr.length() > maxLen){
        		maxLen = valueStr.length();
        	}
        	intArr[i] = Integer.parseInt(valueStr);
        }
        
        int mod = 1, divide = 1;
        for(int i=0; i<maxLen; i++){	// 입력된 값의 최대자릿수만큼 반복.
        	radixGrp = new ArrayList[10];
    		mod = mod * 10;
        	if(i==0){
    			divide = 1;
    		}else{
    			divide = divide * 10;
    		}        	
        	insertRadixGrp(loop, mod, divide);	// Radix그룹에 데이터 넣기.
        	
        	inputToArr();	// map에 들어가며 정렬된 값 배열에 다시 넣기.
        } //end for : 입력된 값의 최대자릿수만큼 반복.
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i : intArr) 
		{
			bw.write(i + "\n");
		}
		bw.flush();
	} //end Asc_10989
	
	void insertRadixGrp(int loop, int mod, int divide){
		for(int j=0; j<loop; j++){	// 배열 하나씩 훑기.
    		int arrJ = intArr[j]%mod/divide;
    		// 각 자릿수그룹에 데이터 넣기.
			if(radixGrp[arrJ] == null){
    			list = new ArrayList<Integer>();
    		}else{
    			list = radixGrp[arrJ];
    		}
    		list.add(intArr[j]);
    		radixGrp[arrJ] = list;
    	} //end for : 배열 하나씩 훑기.
	}
	void inputToArr(){
		int cnt=0;
		for(ArrayList<Integer> eachList : radixGrp){
			if(eachList==null)	continue;
			for(int val : eachList){
				intArr[cnt++] = val;
			}
		}
	} //end inputToArr()
}

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

문제

문제

출처

ICPC

JAVA 기수정렬로 풀고있는데 12%에서 계속 시간초과나요..

pts119 6년 전 0

chogahui05 6년 전 0

pts119 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말