사용자 도구

사이트 도구


ps:problems:boj:2751

수 정렬하기 2

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

기초

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python
제출기록157988KB / 1032ms
최고기록844ms
해결날짜2021/08/24

풀이

  • 그냥 입력받고 정렬해서 출력하면 되는 기초 문제. 수 정렬하기에서 n이 좀더 늘어나서 O(n^2) 소팅 알고리즘으로는 안풀리지만, 어차피 내장된 소트 함수를 사용하는 입장에서는 차이가 없다.
  • 하지만, 출력해야 하는 줄 수가 최대 백만으로 꽤나 크므로, 입출력 최적화를 테스트해보기에 괜찮은 문제이다.
  • 내 경우는 입출력_최적화에서, 코드의 깔끔함을 훼손하는 최적화는 하지 않기로 결론 내린적이 있지만, 이 문제에서는 깔끔함을 유지하면서도 어느정도 최적화가 가능한 부분이 있었다. 수 정렬하기과 비교해보면 인풋을 정수 리스트에 저장해서 소팅하고 출력하는 대신에, 인풋을 문자열 리스트로 저장하고, int값을 키로 주어서 소팅하고 출력하면, 출력할때에 정수→문자열 변환이 사라지기 때문에 꽤나 빨라지는 것을 확인했다. (1500ms 정도에서 1000ms 정도로 단축)

코드

"""Solution code for "BOJ 2751. 수 정렬하기 2".

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

import sys


def main():
    N = int(sys.stdin.readline())
    nums = [sys.stdin.readline() for _ in range(N)]
    print(''.join(sorted(nums, key=int)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O Y S U V
 
ps/problems/boj/2751.txt · 마지막으로 수정됨: 2021/08/31 08:14 저자 teferi