글 읽기 - java 어디서 메모리 초과가 뜨는지 모르겠습니다

june991012 2년 전 0

자바 내장 정렬이 O(nlogn)이니 그것을 사용해서 풀려다가

Counting Sort를 응용해서 풀면 어차피 최대치 최소치 차가 20억이니 20억을 n으로 두고 O(n)으로 풀면 괜찮겠다라고 생각이 들더라구요

그런데 .. 메모리 초과가 떴네요 ㅜㅜ

혹시 20억이라는 수 자체가 문제일까요? 아니면 StringTokenizer를 사용하는 것이 문제인가요?

import java.io.*;
import java.util.StringTokenizer;

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 min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }

        int[] cntarr = new int[max - min + 1]; // 0 -> min의 값. 즉 값에서 -min한 idx에 들어감.
        for(int i = 0; i < n; i++) {
            if(cntarr[arr[i]-min] == 0) cntarr[arr[i] - min]++;
        }

        for(int i = 1; i < max - min + 1; i++) {
            cntarr[i] += cntarr[i-1];
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < n; i++) {
            bw.write(String.valueOf(cntarr[arr[i]-min]-1));
            bw.write(" ");
        }
        bw.flush();
    }
}

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

문제

문제

출처

ICPC

java 어디서 메모리 초과가 뜨는지 모르겠습니다

june991012 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말