글 읽기 - Counting Sort 시간초과에 대해서

nhs0912 7년 전 0

안녕하세요. 수 정렬하기3 에 대해서 질문 하려고요.

다름이 아니라 자꾸 시간 초과가 나와서 어떤 부분에서 시간이 많이 소비되는지 제 소스를 보고 파악을 못하겠네요.

구글링에서 다른 사람들 수 정렬하기3 소스(c++)를 보면 제 소스랑 별로 다른게 없고 단지 언어 차이만 있는거 같은데...

자바 언어가 다른 언어보다는 좀 느리잖아요~

그래서 자바로는 이 문제 못푸는거 아닌가 라는 제 자신을 합리화하게 되네요...ㅠㅠ

제 소스를 보고 어떤 부분을 고쳐야할까요??시간을 좀 더 빠르게 한다면요??

제 소스 간단하게 설명을 한다면

<숫자 카운팅을 하고서 누적까지 했다가 시간이 더 소비 되는거 같아서 제외하였습니다.>

그냥 Counting Sort해서 숫자 갯수만 세고서 바로 그 갯수 만큼 출력하였어요~

package Study;

/**
 * Created by heeseoknoh on 01/01/2017.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    int[] numbers; //입력된 숫자
    int[] countArr;//숫자 세기
    int[] result; //정렬된 후 숫자 저장
    int max = 0;
    int index = 0;

    void inputNumbers() throws IOException {//숫자 입력하기
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        numbers = new int[size];
        for (int i = 0; i < numbers.length; i++) {
            int num = sc.nextInt();
            numbers[i] = num;
            if (max < num) {
                max = num;
            }
        }
    }

    void display(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        //System.out.println();
    }

    void sort() throws IOException {
        inputNumbers();
        int maxNumber = max;
        countArr = new int[maxNumber + 1]; //0-maxNumber+1만큼 생성
        result = new int[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            //해당하는 숫자 카운터
            countArr[numbers[i]]++;
        }


//        for (int i = 1; i < countArr.length; i++) {
//            //누적 숫자 더하기
//            countArr[i] += countArr[i - 1];
//        }


//        for (int i = numbers.length - 1; i >= 0; i--) {
//            //정렬하기
//            result[--countArr[numbers[i]]] = numbers[i];
//            //countArr[numbers[i]]--;
//        }


        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                result[index++]=i;
            }
        }
        display(result);
    }


    public static void main(String[] args) throws IOException {
        new Main().sort();


    }
}

doju 7년 전 1

Java의 입출력 속도는 생각보다 더 많이 느립니다.. Java로 이 문제를 풀려면 BufferedReader, BufferedWriter 등으로 입출력 속도를 개선하지 않으면 불가능해 보입니다.

풀이 자체는 문제의 의도대로 푸신 것 같고, result 배열 없이 countArr 배열만 이용해서 답을 출력하시면 메모리를 아낄 수 있습니다.

nhs0912 7년 전 0

result배열 없이 기존의 숫자가 들어있는 numbers 배열에 정렬된 숫자를 넣어주면 메모리를 아낄수 있다는 말씀이시죠???

doju 7년 전 1

문제가 메모리 제한이 상당히 작길래 덧붙인 말인데, 결국 출력만 하면 되니까 result 배열을 거치지 않고 그냥 i를 countArr[i]번 출력하면 된다는 뜻이었어요.

nhs0912 7년 전 0

답변 감사합니다.

BufferedReader 와 BufferedWriter 사용해서 풀었네요... 정말 Scanner랑 속도 차이가 많이 나나봐요!

덕분에 하나 배워갑니다^^

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

문제

문제

출처

ICPC

Counting Sort 시간초과에 대해서

nhs0912 7년 전 0

doju 7년 전 1

nhs0912 7년 전 0

doju 7년 전 1

nhs0912 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말