[JAVA] 백준 10989번 【수 정렬하기 3】

---

 

문제 자체는 평범한 오름차순 문제이지만, 메모리와 시간 제한이 까다로워서 곰곰히 생각해보고 문제를 풀어봤다.

 

요즘, 정렬 문제를 풀어보면서 StringBuilder 의 위대함을 느끼고 있어서, StringBuilder 를 이용해서 문제를 풀어보았다.

 

방법은 간단하다.

 

StringBuilder 배열을 만들어서, 입력값이 1~10000이라고 했으므로, 입력되는 값을 인덱스로 지정하고 그 인덱스 값에 "\n" 을 추가해서 문자열을 append 해준 후 출력하면 된다.

 

참고로 String str 을 루프 안에서 선언할 경우, 메모리 초과가 일어날 수 있으니 주의해야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(br.readLine());
        String str;
        StringBuilder[] sbArray = new StringBuilder[10001];
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < sbArray.length; i++) {
            sbArray[i] = new StringBuilder();
        }

        for (int i = 1; i <= N; i++) {
        // String str = br.readLine() str 초기화를 루프 안에서 하면, 메모리가 계속 증가해서 메모리 초과 문제가 발생한다.
            str = br.readLine();
            sbArray[Integer.valueOf(str)].append(str + "\n");
        }
        for (StringBuilder sb : sbArray) {
            result.append(sb);
        }
        System.out.println(result);
    }
}

 

메모리 초과의 흔적..

 

하지만, 이 방법 역시, 2432ms 로 시간이 많이 나온 것 같아 다른 사람의 방법을 참고해봤더니

 

int[] 배열에 카운트를 하고 BufferedWriter와 repeat 메서드를 사용하는 방법이 있었다.

 

repeat 메서드를, 완전 초반 입출력 문제를 풀 때 사용했었는데, 이런 단순 문제에는 적극 적용해봐야겠다..

 

엄청난 속도 차이...!

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.valueOf(br.readLine());
        int[] array = new int[10001];

        for (int i = 1; i <= N; i++) {
            array[Integer.valueOf(br.readLine())]++;
        }
        for (int i = 0; i < array.length; i++) {
            bw.write((i + "\n").repeat(array[i]));
        }
        bw.flush();
        bw.close();

    }
}