[백준/Python]정렬 - 수 정렬하기 2, 3

문제

수 정렬하기 2: https://www.acmicpc.net/problem/2751

수 정렬하기 3: https://www.acmicpc.net/problem/10989

---

풀이

[2751]수 정렬하기 2

우선 첫번째 풀이다.

N = int(input())
nums = []

for _ in range(N):
    nums.append(int(input()))

nums.sort()
print(*nums, sep="\n")

갑자기 '시간초과'가 떠버려서 뭔가 했더니, input()때문이었다.

 

나같은 경우 웬만하면 int(input()) 또는 map(int, input().split())으로 해결하는 편인데, 이게 입력받을 데이터가 많은 경우엔 과부하가 걸린단다.

 

input()은 입력값을 받을 때 프롬프트 메시지를 출력하고 사용자의 입력을 기다린다.
이 과정에서 입력 버퍼를 비우고 새로운 입력을 받기 때문에 입력 속도가 상대적으로 느리다.

 

조건을 잘 보면 데이터의 갯수 N은 1<=N<=1,000,000의 범위를 갖는다.
백만건의 데이터가 주어질 수도 있으므로 input()은 적절하지 않다.

 

그럼 뭘 사용하나 했더니 stdin이 있었다.
sys모듈의 stdin.readline()함수를 사용하면 빠른 속도로 입력을 처리할 수 있다.

 

아래는 두번째 풀이다.

import sys


N = int(sys.stdin.readline())

nums = [int(sys.stdin.readline()) for _ in range(N)]
nums.sort()

print(*nums, sep="\n")

입력값을 저장할 리스트 nums도 리스트 컴프리헨션으로 간결하게 처리해줬다.
결과는 성공!

 

다른 해답도 찾아보다가 특이한 코드를 발견했다.
Python3로 풀이한 사람 중 가장 빠른 코드라고 한다.

def sol():
    a=[None]*2000001
    b=map(int,open(0))
    next(b)
    for i in b:a[i]=1
    print("\n".join(str(i) for i in range(-1000000,1000001,1) if a[i]))

sol()

주어지는 수의 값은 절대값이 1,000,000보다 작거나 같은 정수이므로,
-1000000부터 0을 포함하여 1000000까지, 총 2000001개의 [None]으로 이루어진 리스트를 생성한다.

 

그 다음 open(0)으로 값을 입력받고, map()을 통해 int형으로 변환시킨다.

 

나는 이 코드에서 open(0)을 처음 봤다... 신세계.
보통 open()함수는 파일을 읽고 쓸 때 사용하지만, 0을 넣으면 표준 입력을 받을 수 있다고 한다.
즉, sys.stdin == open(0)으로 사용할 수 있다는것이다.

관련 내용들은 아래에서 참고하자 👇
https://neogr.tistory.com/17
https://it-neicebee.tistory.com/118

 

다음줄을 보면 또 신기한 함수가 있다.
next()인데, iterator 객체 요소를 하나씩 읽어올 수 있다.

문제에선 입력 첫줄이 입력값의 갯수(N)이기 때문에, next(b)로 N은 건너뛰고 입력값들만 취급하는것이다.

그럼 b는 첫줄(N)을 제외한 순수 입력값들만 남아있게 되고,
이를 for문으로 순회하며 a[i]=1로 할당하는것이다.

 

마지막으로 a의 존재값들을 "\n".join()으로 출력해준다.

 

실행시간은 692ms로, 내 코드의 절반 가량...
하지만 메모리효율은 더 떨어지니 주의하자.

 

[10989]수 정렬하기 3

통과했던 풀이다.

import sys


nums = [0] * 10001
input = sys.stdin.readline

N = int(input())
for _ in range(N):
    nums[int(input())] += 1

for i in range(10001):
    if nums[i] != 0:
        for _ in range(nums[i]):
            print(i)

수 정렬하기 2와 다르게 중복값이 존재한다.

 

우선 수의 범위에 따라 리스트 nums를 선언해준다.

그 다음 주어진 N값만큼 for문을 반복하며,
nums[입력값]의 값을 1씩 증가시켜준다.

 

이후 범위만큼 for문을 반복한다.
해당 인덱스의 값이 0이 아닐경우, 인덱스의 값 만큼 print(인덱스)를 해주면 된다.

 

아래부터는 실패했던 코드다.

 

첫번째 코드. 시간초과다.

import sys


input = sys.stdin.readline
N = int(input())

nums = [int(input()) for _ in range(N)]
nums.sort()

print(*nums, sep="\n")

간단하게 입력값들을 리스트로 만들어 정렬 후 출력.

 

두번째 코드. 이번엔 메모리 초과였다.

import sys


nums = [0] * 10001
input = sys.stdin.readline

N = int(input())
for _ in range(N):
    nums[int(input())] += 1

print("\n".join(str(i) for i, cnt in enumerate(nums) if cnt for _ in range(cnt)))

잘 보면 출력부분 외엔 통과 코드와 별 다를게 없다.
역시 문제는 출력부분에 있었다.
🚨 join()은 list나 iterable의 모든 요소를 하나의 문자열로 합치는 연산으로, 이 과정에서 메모리 사용량이 증가할 수 있다.

 

+

추가로 개행문자(\n)가 포함된 상태로 map()을 사용하면 에러가 발생한다.

word = 개행문자가 포함된 문자열이라고 치자.
int(word)는 문제가 없다. int()가 개행문자를 제거한 값으로 반환해준다.

하지만 map(int, words)는 에러다.
int()보다 map()이 먼저 실행되기 때문이다. 주의.

---

참고

https://develop247.tistory.com/347

[파이썬/Python] 백준 2751번 수 정렬하기 2

첫번째 풀이도 괜찮고, 두번째 풀이는 신기함. open(), next() 등 평소에 안쓰던 함수를 사용하여 풀었는데, 효율이 좋은가보다.

 

https://lute3r.tistory.com/240

[Python] Baekjoon 백준 2751번 수 정렬하기 2

input()과 sys.stdin.readline()의 차이

 

https://velog.io/@yj_lee/%EB%B0%B1%EC%A4%80-2751%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-2-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 2751번 : 수 정렬하기 2 (파이썬)

합병정렬을 사용한 방식

 

https://kill-xxx.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-3-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC-%EC%98%A4%EB%A5%98-%ED%95%B4%EA%B2%B0

[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결

메모리 초과 해결