[BOJ][JAVA] 10989: 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

import java.io.*;

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 size = Integer.parseInt(br.readLine());
        int[] buffer = new int[10001];
        for(int i=0; i<size; i++){
            int tmp = Integer.parseInt(br.readLine());
            buffer[tmp]++;
        }
        int idx = 1;
        while(size>=0){
            if(idx!=0){
                for(int i=0; i<buffer[idx]; i++){
                    bw.write(idx+"\n");
                }
                idx++;
                size--;
            }
        }

        bw.flush();
        bw.close();
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

들어오는 수가 10000까지니까, 1~10000이 들어갈 배열을 미리 짜서 일종의 계수정렬을 만들어보려고 했다.

아이디어는 잘 짠것같은데 시간초과가 계속 나버렸다.

 

그리고 BufferedWriter를 사용하니까 무슨 이유인지 몰라도 런타임에러가 계속 났다. 위 오답코드에는 없지만 StringBuilder로 작성하니 런타임에러는 아니었고 시간초과가 나는 걸 볼 수 있었다.

---

정답코드

import java.io.*;

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 size = Integer.parseInt(br.readLine());
        int[] buffer = new int[10001];
        for(int i=0; i<size; i++){
            int tmp = Integer.parseInt(br.readLine());
            buffer[tmp]++;
        }

        StringBuilder sb = new StringBuilder();
        for(int j=1; j<=10000; j++){
            while(buffer[j]-- >0){
                sb.append(j).append("\n");
            }
        }
        System.out.println(sb);
    }
}

문제는 출력하는 부분을 어떻게 잡냐였다. 출력할 계수 배열의 크기만큼 돌게 하고, 계수 배열의 원소값을 줄이는 방식으로 출력했다.

StringBuilder를 쓸 때 주의할 점이 있다.

sb.append(j).append("\n");
sb.append(j+"\n");

이 두 줄의 코드가 같다고 생각한다면, 언젠가 시간초과를 보게 될 것이다.

+ 과정에서 String 객체가 매번 생성되는 걸 막기위해 append를 쓰는건데 append 안에 넣어버리면 그 효과를 버리는 짓이 된다. 따라서 개행이 필요하면 개행문자도 append로 넣어줘야한다!

 

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"