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

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

2751번: 수 정렬하기 2

---

문제

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

입력

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

출력

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

 

예제 입력

5
5
4
3
2
1

예제 출력

1
2
3
4
5

풀이 1

import sys
input = sys.stdin.readline

# 입력
n = int(input())

# n개의 정수를 입력 받아 리스트 lst에 저장
lst = [int(input()) for _ in range(n)]

# lst를 오름차순으로 정렬하고, 각 원소를 개행문자와 함께 출력
print(*sorted(lst), sep='\n')

sorted(lst)를 이용하여 lst를 오름차순으로 정렬한 뒤, print() 함수와 * 연산자를 이용하여 각 원소를 개행문자(\n)와 함께 출력한다. 이를 통해 정렬된 수를 한 줄에 하나씩 출력할 수 있다.

이 코드의 시간 복잡도는 O(nlogn)이다.

input() 함수 대신 sys.stdin.readline() 함수를 사용하였기 때문에 입력 부분의 시간 복잡도는 O(n)이다.

다음으로, 리스트를 정렬하는 부분에서 시간 복잡도가 발생한다. 리스트의 크기가 n일 때, sorted() 함수는 평균적으로 O(nlogn)의 시간 복잡도를 갖는다. 따라서 리스트를 정렬하는 부분의 시간 복잡도는 O(nlogn)이다.

마지막으로, print() 함수에서 * 연산자를 사용하였기 때문에, 정렬된 리스트를 출력하는 부분의 시간 복잡도는 O(n)이다.

따라서 전체적인 시간 복잡도는 O(nlogn)이다.

 

큰 수가 입력 될 경우 정렬하는 시간이 너무 오래걸린다. 그렇다면 더 효율적인 방법은 없을까?

입력하는 크기에 따라 극한의 효율을 따져볼 수 있다.

풀이 2

해당 코드는 백준 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()

sol() 함수 내부에서는 다음과 같은 일이 일어난다.

1. 길이가 2,000,001인 리스트 a를 생성한다. 이 리스트는 -1,000,000부터 1,000,000까지의 정수를 인덱스로 가지며, 해당 인덱스의 값이 1인 경우, 입력 파일에서 해당 정수가 등장한 것을 의미한다. 초기값으로는 None으로 모두 초기화된다.
2. open(0) 함수를 사용하여 표준 입력(stdin)을 읽어들이고, map() 함수를 이용하여 정수형으로 변환한다. next() 함수를 이용하여 첫 줄을 제외하고, 남은 줄의 값을 for 루프를 이용하여 하나씩 읽어들이며, 해당 값에 해당하는 a 리스트의 인덱스를 1로 설정한다.
3. -1,000,000부터 1,000,000까지의 정수를 1씩 증가시키며 a 리스트를 순회하면서, 해당 인덱스의 값이 1인 경우, 해당 정수를 출력한다. 즉, 입력 파일에서 등장한 모든 정수를 오름차순으로 출력하는 것이다.

 

이 코드는 입력 파일에서 등장한 정수를 찾아서 출력하는 기능을 수행하는 것으로, 입력 파일의 형식이나 구체적인 사용 용도 등에 따라서 적절한 수정이 필요할 수 있다.

파일을 읽어들이는 방법에는 여러 가지가 있다. open() 함수는 파일을 열고 파일 객체를 반환하는 파이썬 내장 함수 중 하나이다. 이 함수를 사용하면 파일을 읽어들일 수 있으며, map() 함수를 이용하여 한 줄씩 읽어들이는 것이 가능하다.

open() 함수를 이용하여 파일을 읽어들이는 것이 효율적인지는 입력 파일의 크기와 응용 프로그램의 목적에 따라 다르다. 만약 파일 크기가 매우 크고, 한 번에 모든 데이터를 메모리에 로드하기 어려운 경우에는 파일을 일부분씩 분할하여 처리하는 등의 방법이 사용될 수 있다.

b:a[i]=1은 리스트 a의 i번째 인덱스를 1로 설정하는 것을 의미한다. 위 코드에서는 입력 파일에서 읽어들인 값(i)에 해당하는 a 리스트의 인덱스를 1로 설정하여, 해당 값을 등장한 적이 있다는 것을 표시하고 있다. 이를 통해, 나중에 -1,000,000부터 1,000,000까지의 정수를 출력할 때, 해당 값이 a 리스트에서 1로 설정되어 있는지 여부를 검사하여 출력할 값을 결정한다.

해당 코드의 시간 복잡도는 O(N)이다. 이는 입력 파일의 크기에 비례한다. 입력 파일에서 읽어들인 값의 개수를 N이라고 할 때, for 루프가 N번 실행되며, 각 루프에서는 a 리스트의 인덱스를 조회하고, 출력을 수행하는 데 상수 시간이 걸리므로, 전체 시간 복잡도는 O(N)이 된다.

또한 join() 함수를 이용하여 출력을 수행하므로, 출력 시간 복잡도는 출력할 정수의 개수에 비례한다. 출력할 정수의 개수는 입력 파일에서 읽어들인 값의 개수(N)과 같으므로, 출력 시간 복잡도 또한 O(N)이다. 따라서 전체 프로그램의 시간 복잡도는 O(N)이다.

 

참고자료

로그인