항해99, 4주차 나이순 정렬

Today I learned
2022/02/02

회고록

2/02

항해 99, 알고리즘 3주차

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

정렬(Sort)

1. 이론

퀵정렬

퀵 정렬(quick sort) 알고리즘의 구체적인 개념

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 다음의 단계들로 이루어진다.

분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

병합정렬

합병 정렬(merge sort) 알고리즘의 구체적인 개념

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
합병 정렬은 다음의 단계들로 이루어진다.

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

합병 정렬의 과정

추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

2. 문제

문제 설명

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

입력

3
21 Junkyu
21 Dohyun
20 Sunyoung

출력

20 Sunyoung
21 Junkyu
21 Dohyun

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

3. MySol

• merge intervals

import sys


def solution(l):

    l = sorted(l, key = lambda x:x[0])

    for i in range(len(l)):
        print(l[i][0],l[i][1])

    pass

if __name__ == '__main__':

    n = int(sys.stdin.readline())
    l = []
    for _ in range(n):
        age, name = input().split()
        age = int(age)
        l.append([age, name])

    solution(l)

4. 배운 점

• 기본 구현 접근

5. 총평

알고리즘 구현, 정렬 훈련