문제 정보
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
핵심
해당 문제는 시간, 메모리 제한이 걸려있는 문제이며 일반적인 입출력 함수를 사용해서는 쉽게 풀 수 없는 문제이다
따라서 sys 라이브러리를 사용하여 입출력을 진행하거나, 아니면 open(0) 처럼 표준 입출력 함수를 사용하여 문제를 풀어야 할 것이다
이번 고찰에서는 이와 같은 표준 입출력 함수에 대하여 간단하게 설명하도록 하겠다
풀이
a = [None] * 10001
b = map(int, open(0))
next(b)
for i in b:
if a[i] is None:
a[i] = 1
else:
a[i] += 1
for i in range(10001):
if a[i] is not None:
for _ in range(a[i]):
print(i)
풀이는 다음과 같이 풀이하였다
a 배열의 인덱스는 0부터 10,000까지 있는데, 이는 여기에서 정렬에 주어지는 수들이 10,000이하인 수이기 때문이다
여기에서 알 수 있듯, a 배열의 역할은 인덱스에 해당하는 '수' 가 몇개(인덱스에 해당하는 값) 들어있는지 판단하는 역할을 한다
그렇기 때문에, b 배열에 주어진 값들(사용자가 입력한 N(1 ≤ N ≤ 10,000,000)개의 값)을 검사해 가면서 해당 인덱스의 값을 하나씩 올려주며 해당 수가 몇개 들어있는지 검사해 주면 된다
a[i] 가 None이면 자연수 1로 바꾸어 카운팅이 가능하도록 만들어주고, 아니라면 1씩 값을 올려주어 카운팅 해준다
이후 None이 아닌 값들에 해당하는 인덱스(정렬된 수)를 출력해주면 끝이다
고찰
open(0)
표준 입력에서 데이터를 읽는 방법이며, 'sys.stdin.read()' 와 쓰임이 같다.
하지만, 성능의 차이가 있을 수 있는데 `open(0)` 은 파일 디스크립터 0 (표준 입력)을 열고 파일 객체를 반환하고, 이는 I/O동작을 수행하기 때문에 약간의 오버헤드가 발생할 수 있다
또한, 입력을 텍스트로 처리하기 때문에 `int` 와 같은 자료형 변환 작업이 필요함
sys.stdin.read()
`sys.stdin` 에서 입력을 읽고 문자열로 반환함. 파일 객체를 열지 않고 표준 입출력을 처리할 수 있고, 입력을 한 번에 읽어 문자열로 반환하므로 작업이 단순해지고 속도가 약간 더 빠를 수 있다
하지만, 입력이 매우 큰 경우 한번에 모든 입력을 읽는 것은 메모리 사용 측면에서 비효율적일 수 있음
결론
입력의 크기, 성능 요구사항에 따라 선택해야 하나 작은 입력, 대화형 입력의 경우 `sys.stdin.read()`가 더 편리하며 빠를 수 있고
대용량 입력이나 입력을 실시간으로 처리해야 하는 경우 `open(0)` 을 사용하는 것이 더 적합할 수 있음
next(b)
10
5
2
3
1
4
2
3
5
1
7
예제 입력에서 맨 첫번째 값인 10을 무시하고 버린다는 뜻이다
왜냐하면 10이 의미하는 것은 N으로 몇개의 수가 주어졌는지 먼저 명시해주는 역할을 하는데 우리는 `open(0)` 과 같은 표준 입출력 함수를 사용하여 모든 입력을 한꺼번에 읽을 것이므로 몇개의 데이터가 들어오는지 먼저 명시해야 할 필요가 없기 때문이다
b에서 list를 쓰지 않는 이유
b=list(map(int, open(0)))왜 이런식으로 반환된 map 객체를 리스트로 변환해 주지 않을까 하는 생각이 있었는데,
`map(int, open(0))` 을 통해 파일 객체에서 읽은 데이터를 정수로 변환하는 맵 객체를 반환하며, 이 맵 객체는 이터레이터로 필요할 때마다 다음 값을 반환한다. `for loop` 에서 `b`를 이터레이트 하며 값을 사용할 수 있게 된다
반면 `list(map(int, open(0)))` 를 하면 맵 객체의 모든 값을 한번에 읽어와 리스트로 변환하는데, 우리는 최대 10,000,000개의 데이터를 읽어와 리스트로 반환할 것이다
이렇게 되면, `open(0)` 으로 표준 입력을 열고 파일 객체를 반환하는데, 모든 데이터를 한 번에 읽어와서 리스트에 저장하는 것은 메모리 사용 면에서 비효율적이며 입력이 큰 경우 메모리 부족이 발생할 수 있다
`map(int, open(0))` 을 사용하여 이터레이터를 생성하고, for loop을 통해 값이 필요할 때에만 값을 가져오는 방식이 효율적으로 이번 문제를 풀 수 있는 것이다
메모리 초과되었던 지난 나의 풀이에 대한 고찰
a = [None] * 10001
b = map(int, open(0))
next(b)
for i in b:
if a[i] is None:
a[i] = 1
else:
a[i] += 1
print("".join((str(i) + "\n") * a[i] for i in range(10001) if a[i] is not None))`"".join()` 함수가 반복문 안에서 각 반복마다 문자열을 재구성하기 때문에 성능이 저하된 것으로 보인다
import sys
N = int(input())
nums = list(map(int, sys.stdin.readlines()))
for i in sorted(nums):
print(i)당연히 해당 방식으로는 10,000,000개의 숫자를 정렬하는 데에 무리가 있었던 것 같다
댓글