[BOJ] 1427 소트인사이드

#include <cstdio>
#include <queue>
using namespace std;

int main(void)
{
  int c = '0';
  priority_queue<int> q;

  while (c != '\n') {
    scanf("%c", &c);
    if (c >= '0' && c <= '9')
      q.push((int)(c - 48));
  }
  while(!q.empty()) {
    printf("%d", (int)q.top());
    q.pop();
  }
  return 0;
}

입력의 크기는 최대 1,000,000,000이다.

각 자리의 숫자 크기를 비교해 정렬하므로 최대 10개의 숫자를 정렬하게 된다.

그러나 잘못 읽어서 최대 10억개의 숫자를 정렬한다고 생각했다.

위 코드는 priority queue를 사용한 풀이이다.

시간복잡도가 O(nlogn)이므로 1초를 넘길 것 같아 풀면서도 긴가민가했다.

 

우연히 다른 분 코드를 봤는데 10개의 공간을 갖는 int 배열을 만들고 들어오는 숫자를 index로 하여 해당 요소의 수를 증가하는 방법을 사용하셨다.

숫자의 범위는 0부터 9로 명확하고 같은 숫자 간의 순서는 상관 없으며 한 숫자가 10억번 나타나도 int의 표현 범위를 초과하지 않으니 각 index 번호를 요소의 크기만큼 출력하기만 하면 된다.

시간복잡도는 O(n)으로 1초의 제한을 가지고 내가 처음 해석한대로 문제를 풀어야 했다면 이 방법이 바람직하다.

입력을 받는 순간부터 중복되는 연산을 제거할 수 있는지 고려해야겠다.

 

숫자를 출력하는 부분의 코드는 원래 for문으로 작성하였다.

for (int i = 0; i < q.size(); i++) {
  printf("%d", q.top());
  q.pop();
}

그러나 자꾸 숫자가 덜 출력되었다. 4개라면 2개, 7개라면 4개.

for문 안에서 heap의 크기를 출력해보니 한 번 반복할 때마다 1씩 줄어들고 있었다.

pop을 하니 당연한 건데 그걸 조건식에 넣었음을 간과했다.

크기를 저장하는 변수를 만들어 조건식에서 사용하는 방식으로 수정했다.

int n = q.size();
for (int i = 0; i < n; i++) {
  printf("%d", q.top());
  q.pop();
}