[BOJ] 10814. 나이순 정렬

문제

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

10814번: 나이순 정렬

 

 

 

---

어떻게 해도 계속 시간초과가 떠서 정말 다양한 정렬방법을 시도해봤다.

시도해본 정렬 방법에 따라 정리했다.

 

(바로 정답을 보고 싶으면 링크 걸어둔 하단으로 가면 된다!)

 

 

 

주요 아이디어

구조체 사용은 라이브러리 써야해서 안된다

그냥 리스트 형태로 받아서 비교해보자

 

정렬 방법은 일단 제일 간단한 버블정렬부터

 

 

---

 

버블정렬 - 코드 구현 (Python 3)

첫트 - 버블정렬 썼는데 시간 초과 떴음

N = int(input())
members = []

def swap(list, idx):
    (list[idx], list[idx+1]) = (list[idx+1], list[idx])

# append
for i in range(N):
    tmp = input()
    members.append(tmp)

# swap
for i in range(N):
    for j in range(N-1):
        if int(members[j][:2]) > int(members[j+1][:2]):
            swap(members,j)
        elif int(members[j][:2]) > int(members[j+1][:2]) and members[j][3:] > members[j+1][3:]:
            swap(members, j)

# print
for i in range(N):
    print(members[i])

 

 

 

---

 

실패 원인

 

버블정렬.. 구현은 쉽지만 O(n) = n^2로 시간 복잡도가 비교적 크기 때문에 통과가 안된것 같다.

이보다 빠른 정렬 방법으로 다시 구현해보자

 

---

 

주요 아이디어 (2)

퀵정렬 역시 최악의 경우 시간복잡도는 O(n^2) 이지만 평균 복잡도는 O(NlogN)으로 버블 정렬보다 낫기 때문에 사용해본다. 

1. 리스트 안의 피벗 선택
2. 피벗보다 작은 요소들은 모두 피벗 왼쪽
3. 피벗보다 큰 요소들은 모두 피벗 오른쪽
4. 피벗을 제외한 왼쪽 리스트, 오른쪽 리스트 다시 정렬리스트 크기가 0이나 1이 될때까지 반복
5. 부분 리스트에서도 피벗 선정해서 정렬 반복

 

 

 

퀵정렬 - 코드 구현 (Python 3)

 

 퀵정렬 이용 - 시간 초과 (...)

N = int(input())
members = []

def swap(list, i, j):
    (list[i], list[j]) = (list[j], list[i])

def partition(list, l, r):
    low = l+1
    high = r
    pivot = list[l]

    # low와 high가 교차할 때까지 반복
    while low < high:
        print(int(list[low][:2]), int(pivot[:2]))
        while low <= r and int(list[low][:2]) < int(pivot[:2]):
            low += 1
        print(int(list[high][:2]), int(pivot[:2]))
        while high >= l and int(list[high][:2]) > int(pivot[:2]):
            high -= 1
        swap(list, low, high)

    swap(list, l, high)
    return high # 피벗 위치 반환

def quick_sort(list, l, r):
    if l<r:
        # 피벗 위치 q
        q = partition(list, l, r)

        quick_sort(list, l, q-1) # 왼쪽 부분 리스트 정렬
        quick_sort(list, q+1, r)# 오른쪽 부분 리스트 정렬

# append
for i in range(N):
    tmp = input()
    members.append(tmp)

# quick sort
quick_sort(members, 0, N-1)

# print
print("############")
for i in range(N):
    print(members[i])

 

 

---

 

 

주요 아이디어

삽입정렬을 이용. 최적의 경우 O(N) 이고 최악의 경우 O(N^2)

데이터 편차를 많이 탄다고 한다.

 

 

 

삽입 정렬 - 코드 구현 (Python 3)

N = int(input())
members = []

def insertion_sort(arr):
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        print(int(arr[i - 1][:2]))
        while (i > 0) and (int(arr[i - 1][:2]) > int(to_insert[:2])):
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert

# append
for i in range(N):
    tmp = input()
    members.append(tmp)

# insertion_sort(members)
insertion_sort(members)

# print
for i in range(N):
    print(members[i])

 

역시나 시간 초과...

 

 

---

 

주요 아이디어

여태껏 구현해본적 없던 새로운 정렬방법 사용해보기로 했다!

 

 

기수 정렬 (Radix Sort)

 

낮은 자리수부터 비교해서 정렬해간다는 것을 기본 개념으로 하는 정렬 알고리즘

-> 비교 연산을 하지 않으며 속도가 O(N)으로 매우 빠르지만 추가 메모리를 필요로 함

 

• 0~9까지의 버킷 (큐) 을 준비
• 모든 데이터에 대해 가장 낮은 자리수에 해당하는 버킷에 차례로 데이터 두기
• 0부터 차례대로 버킷에서 데이터를 다시 가져옴
• 가장 높은 자리수를 기준으로 해 자리수를 높여가며 2~3번 과정 반복

참고자료 : https://lktprogrammer.tistory.com/48

 

 

 

기수 정렬 - 코드 구현 (Python 3)

 

# 리스트와 파이썬 내장 큐 메서드 (pop, append) 사용
N = int(input())
members = []

def radix_sort(members):
    Bucket = [[], [], [], [], [], [], [], [], [], []] # 10개의 이중 리스트 추가
    sorted_members = []
    final_sorted_members = []

    # 1의 자릿수
    for member in members:
        age = int(member[:2])
        Bucket[age%10].append(member)

    # 0번 큐부터 차례로 데이터 가져와서 원래 배열에 넣어줌
    for Q in Bucket:
        while len(Q) != 0:
            sorted_members.append(Q.pop(0))
    
    #print('1의 자릿수 정렬 :', sorted_members)

    # 10의 자릿수
    for member in sorted_members:
        age = int(member[:2])
        Bucket[age//10].append(member)
    
    # 0번 큐부터 차례로 데이터 가져와서 원래 배열에 넣어줌
    for Q in Bucket:
        while len(Q) != 0:
            final_sorted_members.append(Q.pop(0))
    
    #print('10의 자릿수 정렬 :', final_sorted_members)
    return final_sorted_members
    

# append
for i in range(N):
    tmp = input()
    members.append(tmp)

sorted_members = radix_sort(members)


# print
for i in range(N):
    print(sorted_members[i])

 

 

# 파이썬 라이브러리 deque 사용

from collections import deque

N = int(input())
members = []

def radix_sort(members):
    buckets = [deque() for _ in range(10)]
    nums = [int(x[:2]) for x in members]

    max_val = max(nums)
    Q = deque(members)
    cur_ten = 1

    while max_val >= cur_ten:
        while Q:
            member = Q.popleft()
            num = int(member[:2])
            buckets[(num // cur_ten) % 10].append(member)

        for bucket in buckets:
            while bucket:
                Q.append(bucket.popleft())

        cur_ten *= 10

    return list(Q)

# append
for i in range(N):
    tmp = input()
    members.append(tmp)

sorted_members = radix_sort(members)

# print
for i in range(N):
    print(sorted_members[i])

 

 

안타깝게도 이건 틀렸습니다가 떴다.. 원인 찾기가 너무 힘들어서 일단은 보류했다

-> 그래도 시간초과 안떴으니까 이건 가능성이 있을듯하다!! 

// 오류 예시 찾아볼 것 

 

 

 

주요 아이디어

파이썬 내장 메서드를 이용한다

구글 서치 결과 이 방법을 제일 많이 쓰는듯 하다!

 

 

 

내장 메서드 - 코드 구현 (Python 3)

내장 메서드 이용 

 

N = int(input())
members = []

# append
for i in range(N):
    age, name = map(str, input().split())
    age = int(age)
    members.append((age, name))

members.sort(key=lambda x : x[0])

# print
for i in members:
    print(i[0], i[1])

 

 

 

 

 

제출 결과

 

 

---

 

코드 개선 방안

• 내장 메서드 사용방법 말고 다른 정렬 방법을 여러가지 시도해보았다
• 기수정렬 오류 원인 찾고 다시 풀어볼 것!