[백준 11단계] 2750, 2751 수 정렬하기

🥕 [ 백준 2750, 2751 ] 수 정렬하기

문제 링크

url : https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

문제 링크

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

2751번: 수 정렬하기 2

🍒 문제 분석

수 정렬하기 1.

시간제한 1초, N은 1000까지만 주어진다.

\( O(N^2) \) 으로 풀라고 문제에 명시

 

수 정렬하기 2.

시간제한 2초, N <= 1,000,000

\( O(NlogN) \) 으로 풀라고 문제에 명시

 

🥑 코드

1-1. 버블 정렬

N = int(input())
mylist = []
for _ in range(N):
    mylist.append(int(input()))

# 버블 정렬 ver.
for i in range(len(mylist)-1):                     # i랑 i+1이랑 비교하니 len(mylist)-1 까지만 본다.
    for j in range(i+1,len(mylist)):
        if mylist[i] > mylist[j] :
            mylist[i], mylist[j] = mylist[j], mylist[i]
for i in mylist:
    print(i)

1-2. 삽입 정렬

if len(mylist)==1:                                      # 요소가 하나일 때는 삽입정렬을 쓸 수 없다.
    print(mylist[0])

else:
    # 삽입 정렬 ver.
    for i in range(1,len(mylist)):                      # 0번째 요소는 정렬 되어있음
        for j in range(i,0,-1):
            if mylist[j-1]>mylist[j]:
                    mylist[j-1],mylist[j] = mylist[j],mylist[j-1]
    for i in mylist:
        print(i)

1-3. 선택 정렬

# Selection sort
for i in range(len(mylist)-1):
    minitem = mylist[i]
    minindex = i
    for j in range(i+1,len(mylist)):              # 최솟값을 찾아내어 리스트 가장 앞과 바꾼다.
        if mylist[j] < minitem:
            minitem = mylist[j]
            mylist[minindex],mylist[j] = mylist[j],mylist[minindex]
for i in mylist:
    print(i)

2-1. 병합 정렬  ( 시간 초과 )

N = int(input())
mylist = [input().strip() for _ in range(N)]

# 병합 정렬
def merge1(datas):
    if len(datas)==1:
        return datas
    mid = len(datas)//2
    left = merge1(datas[:mid])
    right = merge1(datas[mid:])
    mergelist = []
    i, j = 0,0
    while True:
        if i == len(left):
            mergelist += right[j:]
            break
        elif j == len(right):
            mergelist += left[i:]
            break
        elif left[i]<right[j]:
            mergelist.append(left[i])
            i += 1
        else : 
            mergelist.append(right[j])
            j += 1
    return mergelist

[print(i) for i in merge1(mylist)]

 

2-2 퀵 정렬 (시간초과)

def quick_sort(datas,start,end):
    if start >= end:
        return
    pivot = start
    left = start+1
    right = end
    while (left <= right):
        while (left<=end) and (datas[left]<=datas[pivot]):  #끝까지 가면 len(datas) 까지 간다.
            left+=1
        while (right>start) and (datas[right]>=datas[pivot]): #끝까지 가면 0 까지 간다.
            right-=1
        if left > right :
            datas[right], datas[pivot] = datas[pivot], datas[right]
        else:
            datas[right], datas[left] = datas[left], datas[right]
            datas
    quick_sort(datas,start,right-1)
    quick_sort(datas,right+1,end)

N = int(input())
mylist = [input() for _ in range(N)]
quick_sort(mylist,0,len(mylist)-1)
[print(i) for i in mylist]

 

 

🍉 깨달은 점 및 정리

정렬 함수를 다시 쓰는데 시간이 매우 오래걸렸다.

자주 복습해야함을 느꼈다.

 

수 정렬하기 2 의 경우

병합 정렬과 퀵 정렬 모두 시간초과가 났다...

 

와이파이 문제거나 또는 힙정렬과 같은걸 써봐야할거 같은데

주말에 다시 한번 풀어봐야겠다..