이제, 한 해가 얼마 남지 않았다. 올해를 실버로 마무리 하는 것은 조금 아쉽지만 내년에는 더 열심히 해보겠다

기억에 남는 문제들

[Bronze I] 수 정렬하기 3 - 10989

수 정렬하기 3 - 10989

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

내가 푼 문제 중 단연코 가장 어려웠던 문제가 아니었나 생각한다
왜냐하면,, 메모리와 시간에 대한 제한이 강하게 걸려있기 때문이다
심지어 정답비율이 23.861%로 굉장히 낮은 수치를 가지고 있는데 왜 브론즈 1일까 싶다.. ㅎ

문제 자체는 굉장히 단순하다
N과 N개의 수를 주고 이를 오름차순으로 정렬하는 것이다

그러나, 메모리와 시간에 대한 제한이 해당 문제를 까다롭게 만든다

처음 문제를 보고 나는 또 정렬 문제야? 하며 java.util 패키지를 import해와 가볍게 정렬시키고 넘기려고 했다

for (int i=0; i<N; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }

    Arrays.sort(arr);

    for (int i=0; i<N; i++) {
      System.out.println(arr[i]);
    }

그러나, 끊임없는 시간 초과의 늪에 빠지게 되었다..

결국 나는 총 두가지 측면에서 이를 줄여보고자 하였다

첫째는 임포트해온 패키지 - 정렬 자체에 대한 고민이었다
Arrays.sort() 자체의 시간 복잡도는 NlogN을 갖는다
해당 문제에서 N의 최대값는 10의 7승까지 주어지기에 Arrays.sort()를 사용하면 시간 초과가 발생할 가능성이 높다
10의 7승개의 데이터들을 받고 sort하려다보니 오류가 발생한게 아닐까? 하는 고민으로부터 비롯한 것이었다

즉, 여기서는 계수 정렬 알고리즘을 사용하여 시간 복잡도를 N+k로 줄여보고자 한다
1 ~ 10000이라는 범위 제한이 걸려있으므로 해당 값을 1씩 카운트해주는 방식을 선택하였다

두번째은 출력에 대한 고민이었다
입력값을 버퍼로 받는 만큼 출력값 또한 버퍼에 저장하여 이를 한번해 뱉어내는 방식을 생각했다

최종 코드

    for (int i=0; i<N; i++) {
      arr[Integer.parseInt(br.readLine())] += 1;
    }

    for (int i = 1; i <= 10000; i++) {
      while (arr[i] > 0) {
        bw.write(i + "\n");
        arr[i] -= 1;
      }
    }

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

SIVER - 정렬 문제들

정렬 문제를 몇개 풀다보니 조건의 우선순위를 부여하는 문제들이 나타났다
가령, A에 따라 정렬 후 두 값이 동일하다면 B에 따라 정렬하라는 식이었다

해당 구조를 알고 있으면 좋을 것 같아 정리를 해보았다

Arrays.sort(array, (a, b) -> {
    if (조건1) return 비교결과1;
    return 비교결과2;
});

기본적인 구조는 다음과 같다

이때 return 값에 Integer.compare이나 String.compareTo를 사용하여 두 개의 값을 비교해준다
Integer.compare를 사용하여 정수 직접 비교시 범위를 벗어나 오버플로우가 발생하는 것을 방지하여 주어쏙
String.compareTo를 통해 문자열을 사전 순으로 비교하게 되었다

해당 구조의 시간 복잡도는 평균 NlogN의 시간 복잡도를 갖고 있기에 주로 이것을 사용할 것이며, 만약 데이터가 정수이고 값이 제한적이라면 Counting sort하지 않을까 싶다

결론

메소드를 잘 외워두면 손해는 보지 않는다