[BOJ 10825] 정렬(Sort Application)

📍 정렬 조건

✔️ 조건1 : 정렬 조건이 필요하다

자료들이 주어졌을 때, 뭐가 앞에 와야되는지

✔️ 조건2 : 시간 복잡도는 약 O(NlogN)이다

N개의 원소를 정렬하는 것은 O(NlogN)만큼의 시간 복잡도를 갖는다.

✔️ 조건3 : In-place / Stable 여부를 알아야 한다.

1. 정렬 알고리즘이 In-place(제자리)한가?

• 정렬 하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?
• ex) 정렬 해야하는 원소 개수: 10만개, 필요한 메모리 10개 => In-place(메모리 무시할만한 크기)
• 정렬 해야하는 원소 개수: 10만개, 필요한 메모리 10만개 => not In-place(메모리 무시 크기 무시 X)

2. 정렬 알고리즘이 Stable(안정)한가?

• 동등한 위상의 원소들의 순서 관계가 보존되는가?
• ex) A배열은 5원소 2개(5-1, 5-2) 가지고 있음 => 정렬 후에도 5-1이 5-2보다 먼저 정렬되어야 함.

📍 정렬 특성

• 같은 정보들은 인접해 있을 것이다.
• 각 원소마다, 가장 가까운 원소는 자신의 양 옆 중에 있다.

📍 PYTHON 정렬 함수 & lambda

- sort()

< list >.sort(key = <function>, reverse = <bool>)

• 원본 자체를 수정하며, 반환값 없음
• sort함수는 inplace함수로 아무것도 리턴하지 않고, 기존 리스트 자체에서 정렬이 이루어짐

- sorted()

sorted( <list> , key = <function> , reverse = <bool>

• iterable 자료형에 대해 정렬 가능
• list 자료형으로 return
• 기존의 리스트는 건드리지 않고, 정렬된 새로운 리스트를 반환함 => 정렬 결과를 다른 변수에 따로 받고 싶은 경우 유용하게 쓰임

이처럼 lambda 함수를 이용하면 특정한 기준으로 정렬하는 대부분의 문제를 해결할 수 있다는 점을 기억하자!

✔️ 2중 리스트에서의 다중조건 정렬

• key 값으로 정렬
• key = lambda x : x[0]
  => 0번째 원소를 기준으로 오름차순 정렬
• key = lambda x : -x[0]
  => 0번째 원소를 기준으로 내림차순 정렬

✔️ key가 여러개 일 때?

• key = lambda x: (x[0] , x[2])
• x[0]을 우선순위로 정렬 후, x[0]이 같으면 x[2]를 기준으로 다시 정렬!

📍 BOJ 10825 - 국영수

난이도 1

문제

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

🛠 문제 파악하기 - 정답의 최대치

형 결정 (입력 조건)
1 <= 모든점수 <= 100 => Integer 사용해도 충분하다!

🛠 시간, 공간 복잡도 계산하기

정렬만 하면 되니깐 O(NlogN)

• NlogN <= 100,000 * log100,000 = 1,600,000
• 즉 1초안에 충분히 가능한 연산이다!

🛠 리스트의 원소들을 정렬할 때는 람다(lambda) 함수 이용하기

• 이 문제는 정렬 문제를 공부하는데 필수로 풀어야 할 문제이다.
• 문제의 조건을 살펴보면 N이 최대 100,000이고 시간제한이 1초이다. 이는 O(N^2)로 풀지 말고 다른 방법으로 풀라는 뜻이다.
• 파이썬 정렬 라이브러리는 O(NlogN) 시간복잡도를 가지므로 시간 초과가 나지 않고 문제를 풀 수 있다.
• 따라서 정렬 라이브러리인 sort()함수를 이용하여 lambda 함수로 해결한다.
• lambda 함수의 기본 형식은 list.sort(key=lambda x:(정렬대상)) or
• sorted(list, key=lambda x:(정렬 대상))이다.

코드1

import sys
n = int(sys.stdin.readline())
array = [list(map(str, sys.stdin.readline().split(' '))) for _ in range(n)]
sorted_array = sorted(array, key = lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for arr in sorted_array:
    sys.stdout.write(arr[0])
    sys.stdout.write('\n')

✨ 코드2 (클래스-구조체)

import sys

class Elem:
    def __init__(self, name, korean, english, math):
        self.name = name
        self.korean = korean
        self.english = english
        self.math = math

n = int(sys.stdin.readline())
a = []

for i in range(n):
    inp = sys.stdin.readline().split()
    inp[1:] = map(int, inp[1:])		# 이름 inp[0] 빼고 int형으로 변환 
    a.append(Elem(*inp))

a.sort(key = lambda x: (-x.korean, x.english, -x.math, x.name))

names = [elem.name for elem in a]
for name in names:
    print(name)

참고
https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline
https://velog.io/@hyejin_nk/파이썬-sorted-정렬-조건-다중-조건
https://data-flower.tistory.com/89