사용자 도구

사이트 도구


ps:problems:boj:10989

수 정렬하기 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호10989
문제명수 정렬하기 3
레벨실버 5
분류

기초

시간복잡도O(n)
인풋사이즈n<=10,000,000
사용한 언어Python
제출기록29452KB / 5836ms
최고기록4264ms
해결날짜2021/08/25

풀이

  • 그냥 입력받고 정렬하고 출력하면 되는 문제이긴 한데.. 카운팅 소트를 써야만 하는 문제이다.
  • n제한이 백만이었던 수 정렬하기 2에서도 카운팅 소트로 구현한 코드가 살짝 더 빠르게 돌아가는걸 보긴 했었는데, 이문제는 n 제한이 10배로 늘었고.. 그리고 무엇보다도 메모리 제한이 걸려서 모든 수를 다 메모리에 읽어 들이는 것이 불가능하다. 수의 범위가 10000 이하이므로 크기 10000짜리 배열에 각 숫의 등장 횟수를 저장하면 된다
  • 출력해야 할 라인도 천만라인이기때문에, 출력을 최적화 하는 것이 큰 영향을 미친다. 그러나 출력을 최적화하는 방식인, 문자열에 출력할 내용을 모두 저장해놓고 한번에 출력하는 것은, 메모리 제한때문에 역시 불가능하다. 그냥 한줄씩 출력해도 통과하는데에는 별 문제는 없다. 빠른 코드들은 한줄씩 출력하는 대신, X줄씩 버퍼용 문자열에 저장해놓고 버퍼만큼씩 한번에 출력하는 방식으로 속도를 높였다. 하지만, 그렇게까지 귀찮게는 하기 싫을때 쓸 수 있는 함수로 sys.stdout.writelines가 있다. 얘는 문자열의 이터레이터를 인자로 받아서 출력해주는데, 긴 문자열 하나로 만들어서 print로 출력한것보다는 약간 느리지만 그래도 줄 수만큼 print를 호출해서 출력하는 것보다는 훨씬 빠르게 출력해준다. 평소에는 굳이 귀찮게 이런 함수를 쓸일이 없지만, 이 문제의 경우에는 이터레이터를 사용해서 메모리를 아끼면서도 빠르게 출력이 가능하다.

코드

"""Solution code for "BOJ 10989. 수 정렬하기 3".

- Problem link: https://www.acmicpc.net/problem/10989
- Solution link: http://www.teferi.net/ps/problems/boj/10989
"""

import itertools
import sys

MAX = 10000


def main():
    N = int(sys.stdin.readline())
    count_by_num = [0] * (MAX + 1)
    for _ in range(N):
        num = int(sys.stdin.readline())
        count_by_num[num] += 1    
    sys.stdout.writelines(
        itertools.chain.from_iterable(
            itertools.repeat(f'{num}\n', count)
            for num, count in enumerate(count_by_num)
            if count > 0))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N F Q᠎ F L
 
ps/problems/boj/10989.txt · 마지막으로 수정됨: 2021/08/31 08:44 저자 teferi