Coding Test/Sort
[2751] 수 정렬하기2 (1 ≤ N ≤ 1,000,000, abs(K) ≤ 1,000,000, 병합 정렬)
Karla Ko
2023. 6. 6. 11:38
728x90
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
분석
N(1 ≤ N ≤ 1,000,000) nlogn 병합정렬로 풀이
시간복잡도, 시간제한, 빅오(Big-O) 표기법
1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만
karla.tistory.com
풀이
import sys
input=sys.stdin.readline
n=int(input())
a=[]
for _ in range(n):
a.append(int(input()))
tmp=[0]*n # 정렬용 임시 리스트
# 병합정렬
def mergeSort(s,e):
if e-s<1:return
m=int(s+(e-s)/2) # 중간점
# 재귀함수 형태로 표현
mergeSort(s,m)
mergeSort(m+1,e)
for i in range(s,e+1):
tmp[i]=a[i]
# 정렬할 a리스트 인덱스
j=s
# 투 포인터
idx1=s
idx2=m+1
# 두 그룹을 병합
while idx1<=m and idx2<=e:
if tmp[idx1]>tmp[idx2]:
a[j]=tmp[idx2]
j+=1
idx2+=1
else:
a[j]=tmp[idx1]
j+=1
idx1+=1
# 한쪽 그룹이 모두 선택된 후 남아있는 값 정리
while idx1<=m:
a[j]=tmp[idx1]
j+=1
idx1+=1
while idx2 <= m:
a[j] = tmp[idx2]
j+=1
idx2+=1
mergeSort(0,n-1)
for x in a:
print(x)
728x90