오늘의 문제
https://www.acmicpc.net/problem/2751
포인트 쳌쳌
- O(NlogN) 이하의 시간 복잡도를 가진 알고리즘을 사용할 것.
- 시간복잡도가 O(N^2)인 선택, 삽입, 버블 정렬은 시간초과로 이 문제를 통과할 수 없다.
- 이 문제에 대한 FAQ를 참고해서 풀어야 할 것 같다.
나는 파이썬의 정렬 함수인 sort, sorted()를 먼저 사용하여 제출해보았으나 채점할 때 1%에서 멈춰있다가 시간초과로 실패했다.
FAQ글을 보면 이 문제를 파이썬으로 풀면 매우 느려서 PyPy2 나 PyPy3로 제출하는 것을 권장한다고 한다.
그래서 나는 sort()로 푼 코드를 PyPy3로 제출해야 통과할 수 있었다.
sort() 사용 풀이 코드
n = int(input())
num = []
#리스트 만들기
for i in range(n):
num.append(int(input()))
num.sort()
#sorted(num) 과 같다.
#결과 출력
for i in num:
print(i)
병합 정렬 풀이 코드
병합정렬개념 정리한 것을 바탕으로
병합 정렬로도 이 문제를 구현하여 제출해보았다.
다양한 풀이들이 있었지만
병합 정렬은 중앙값을 기준으로 왼쪽그룹, 오른쪽 그룹을 재귀로 쪼갠 다음 에 각 그룹의 원소를 순서대로 크기 비교하며 작은 것 먼저 리스트에 저장 하는 것이 포인트인 것 같다.
아 이 코드 또한 PyPy3로 제출하였다.
혹시나 했지만 역시나 Python3로 제출하면 1%에 머물다가 시간초과가 나버린다.
n = int(input())
num = []
#리스트 만들기
for i in range(n):
num.append(int(input()))
def merge(left, right):
i = 0
j = 0
v = [] #정렬된 값을 저장하는 공간
while i < len(left) and j < len(right):
#두 그룹의 현재 요소 크기 비교에 따라 v에 값 저장
if left[i] <= right[j]:
v.append(left[i])
i += 1
else:
v.append(right[j])
j += 1
#left그룹을 모두 조회했다면 right의 남은 요소들을 추가
if i == len(left):
v = v + right[j:]
#right그룹을 모두 조회했다면 left의 남은 요소들을 추가
if j == len(right):
v = v + left[i:]
#정렬 완료한 v리스트를 리턴
return v
def mergeSort(a):
#원소가 하나라면 정렬이 필요없으므로 그대로 반환
if len(a) <=1:
return a
middle = len(a) // 2 #중간값
left = mergeSort(a[:middle]) #중간값 기준 왼쪽 그룹
right = mergeSort(a[middle:]) #중간값 기준 오른쪽 그룹
return merge(left, right)
result = mergeSort(num)
#출력 결과
for i in result:
print(i)
채점 결과
아무래도 직접 구현한 코드(위에서 두번째)보다는
내부함수 sort()를 써서 통과한 코드(위에서 세번째)의 시간이 더 짧게 걸렸다.
