백준_10989 수 정렬하기 3 (기수 정렬) - 실패(메모리초과)

 

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

public class BJ_10989 {

    public static void main(String[] args) throws IOException {

        int n, i, k, j, num, ind;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        Queue<Integer> resultQ = new LinkedList();
        Queue<Integer>[] arr = new Queue[10];

        for(i=0; i<10; i++) {
            arr[i] = new LinkedList<>();
        }

        for(i=0; i<n; i++) {
            resultQ.add(Integer.parseInt(br.readLine()));
        }

        for(i=0; i<5; i++) {
            k = (int)(Math.pow(10,i));

            while(!resultQ.isEmpty()) {
                num = resultQ.poll();
                ind = (num / k) % 10;
                arr[ind].add(num);
            }

            for(j=0; j<10; j++) {
                while(!arr[j].isEmpty()) {
                    resultQ.add(arr[j].poll());
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!resultQ.isEmpty()) {
            sb.append(resultQ.poll()).append('\n');
        }

        System.out.println(sb);
    }
}

 

메모리 초과

 

너무 잘 풀린다 싶었는데 메모리 초과

메모리 제한이 좀 빡센 문제다.

아무래도 배열 한개 안에 10개의 연결리스트를 사용하는게 무리였던 듯 하다.

 

말고는 모르겠어서, 풀이코드를 참고해서 개선했다.

https://kjyyjk.tistory.com/237

 

10989번: 수 정렬하기 3