백준 10989. 수 정렬하기 3

문제 링크

난이도	정답률(_%)
Silver 4	22.878%

설계 및 풀이

• 총 숫자의 개수 N 10,000,000
• 숫자의 범위 1 ~ 10,000

1. 처음엔 TreeMap을 이용하면 key값 순서대로 내부에서 정렬이 되기 때문에 이를 이용해 저장된 value의 개수만큼 순서대로 출력하려고 했으나 시간초과 발생.
2. 숫자의 개수가 너무 많아서 정렬을 시도하면 시간초과가 발생하기 때문에 숫자의 범위가 10,000개 인 것을 고려해 길이가 10001인 배열을 생성, 숫자를 개수만큼 저장하고 10,000번을 순회하면서 개수만큼 출력하는 방식을 이용하였다.

시간 복잡도

O(N)

공간 복잡도

int형 배열 길이 10001

새롭게 알게 된 것

• Integer.toString() vs String.valueOf()
  • 동료가 아래에 하이라이팅 된 23번째 줄, Integer.toString()를 쓴 부분에서 String.valueOf()로도 사용이 가능하겠다고 리뷰를 해줬다. 원래 알고있던 방법이긴 했지만 이렇게 보니 두가지 기능이 어떤 차이가 있을지 궁금해져서 한번 찾아봤다.
  • 가장 큰 차이점은 Integer.toString()은 parameter에 값이 없으면 NullPointerException이 발생하지만 String.valueOf()는 그렇지 않다고 한다. 값을 보장할 수 없는 경우가 있다면 후자를 이용하는 것이 더 안전할 것이다.
  • 어떤게 더 낫냐는 부분에서는 String.valueOf()에는 여러가지 타입이 가능해서 변화가 적어서 좋다는 분들도 있고, 내부적으로는 어차피 Integer.toString()을 호출해서 이게 더 낫다는 분들도 있고 다양한 의견들이 있었다.. 취향차이인듯🤔
  • Stack overflow 글 참고!

코드

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

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 totalCount = Integer.parseInt(br.readLine());
        int[] numbers = new int[100001];

        for (int i = 0; i < totalCount; i++) {
            int currentNumber = Integer.parseInt(br.readLine());

            numbers[currentNumber] += 1;
        }

        for (int i = 1; i < numbers.length; i++) {
            for (int j = 0; j < numbers[i]; j++) {
                bw.write(Integer.toString(i) + "\n");
            }
        }

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