[코딩 테스트 연습(파이썬/Python)] 백준 2750번 _ 수 정렬하기1, 2, 3

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

[문제]

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

[입력]

수 정렬하기 1: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

수 정렬하기 2: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

수 정렬하기 3: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

[아이디어]

sort()

 

# 1, 2만 통과 가능
import sys
s = list(map(int, sys.stdin.readlines()[1:]))
s.sort()
for n in s:
    print(n)

수 정렬하기 3의 경우 메모리 제한이 빡세서, 위의 방법으로 통과할 수 없다. 문제 3의 핵심은 수들 간의 중복이 가능하다는 점이다. 동일한 숫자가 최소 1000번은 반복되므로, 이를 모두 배열에 담아 메모리를 차지하는 것이 비효율적이고 이에 대한 해법이 필요하다. 어차피 동일한 숫자는 등장한 횟수만큼 출력해야하므로, 사전을 이용하면 해결이 가능해 보인다.

# 시간초과
n = int(input())
d = dict()
for _ in range(n):
    a = int(input())
    d[a] = d.get(a, 0) + 1
for x in sorted(d):
    for _ in range(d[x]):
        print(x)

사전에 각 숫자를 key로, 나온 횟수를 value로 등록한 뒤 value만큼 key의 출력을 반복하는 코드다. 시간초과가 났다.

import sys
n = int(input())
d = dict()
for _ in range(n):
    a = int(sys.stdin.readline())
    d[a] = d.get(a, 0) + 1
for x in sorted(d):
    for _ in range(d[x]):
        print(x)

입력 받는 방식만 바꾸었더니 통과가 됐다. 개인적으로 입력 받는데 sys 모듈을 사용하지 않는 차이로 시간초과가 나는 문항은 없으면 좋겠지만,, 어쨌든 입력 받는 방식의 차이 때문에 통과 여부가 달라지는 문제를 처음 접했다.