[BOJ] Python 백준 2751번 수 정렬하기 2 실버 5

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

2751번: 수 정렬하기 2

문제 풀이

---

문제 자체는 단순하다.

 

입력으로 받는 데이터를 그대로 오름차순으로 정렬해서 출력하면 되기 때문이다.

 

다만 문제의 조건에서 수의 개수는 1000000개 이하, 각 수는 절댓값이 1000000보다 작거나 같은 정수이기 때문에 인덱스로 접근하는 방식은 256MB로 제한되어 있는 메모리에서 너무 많은 공간을 차지하여 불가능하고 결국 정렬하는 방법밖에 없다.

 

하지만 파이썬을 사용하기에 상당히 유용한 정렬 함수를 사용할 수 있다는 이점이 있다.

 

바로 기본 라이브러리로 제공하는 sort, sorted 함수이다.

 

이 함수들은 파이썬 내부에서 삽입 정렬과 병합 정렬을 섞은 방식으로 작동하도록 되어있어 최악의 경우에도 O(nlogn)이라는 효율적인 시간 복잡도를 나타낸다.

 

O(nlogn)의 시간 복잡도를 나타내는 정렬 방식을 직접 구현하려면 다소 복잡하고 시간도 걸리기에 알아두면 자주 유용하게 사용할 수 있다.

 

두 함수의 차이점은 sort는 원본 리스트를 정렬하고 sorted는 원본 리스트는 변함없이 정렬된 리스트를 반환한다는 점이다.

 

또한 해당 함수들의 인자로 key를 사용할 수 있다.

 

num_list=[[1,2],[2,2],[1,1],[2,1]]
num_list.sort(key = lambda x : (x[1],-x[0]))

이렇게 사용하면 정렬할 때 각 원소들의 1번째 인덱스를 기준으로 오름차순, 1번째 인덱스가 같다면 0번째 인덱스를 기준으로 내림차순으로 정렬하겠단 의미이다.

 

해당 정렬방법은 코딩 테스트에도 유용하게 쓰이고 필자도 사용한 적이 많으므로 반드시 익숙해지는 것을 권장한다.

 

다음은 문제를 통과한 전체 코드이다.

 

num=int(input())
numbers=[]
for i in range(num):
    numbers.append(int(input()))
for i in sorted(numbers):
    print(i)

 

정답률이 30%인 문제 치고 상당히 짧고 간결한 코드가 나왔다.

 

numbers 리스트에 원소들을 입력받고 sorted로 numbers를 정렬한 리스트를 반복하며 출력할 뿐이다.

 

이때 numbers를 정렬한 리스트를 다시 사용할 필요가 없어서 sorted를 썼지만 재사용해야 한다면 새로운 변수에 정렬한 리스트를 할당하든가 sort로 원본 리스트를 정렬하든가 문제 상황에 맞게끔 적용하는 것을 주의해야 한다.

 

또한 Python3 자체가 다소 느리기 때문에 제출은 PyPy3로 했다.

 

분명 맞는 코드 같은데 시간 초과가 뜬다면 PyPy3로 제출해보는 것을 권장한다.

 

결과 화면

 

관련 문제인 10989번 수 정렬하기 3은 비슷한 문제지만 조건에서 차이가 나기 때문에 다른 방식으로 풀었다.

 

해당 문제를 풀어보고 만약 막혔다면 풀이 방식에서 도움받으면 좋을 것 같다.

 

https://khsung0.tistory.com/38

[BOJ] Python 백준 10989번 수 정렬하기 3 실버 5