📍In a nutshell ...
lambda 함수는 익명함수로, 정렬 문제가 이를 활용해볼 수 있는 좋은 예시다- 함수를 따로 정의하지 않고, lambda 식을 통해 비스무리하게(?) 구현할 수 있다.
- 한번 사용하고 끝나기 때문에 함수보다 메모리 사용이 효율적이다.
- 오름차순 예시 :
lambda x : x[0] - 내림차순 예시 :
lambda x : -x[0]
- 안정정렬과 불안정정렬이 존재한다
- 안정정렬은 같은 값을 갖는 record가 여러 개 존재할 때, 원래의 정렬을 보장한다
- 불안정정렬은 원래의 정렬을 보장해주지 못한다
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다.
나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고,
길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
풀이
가장 먼저 나이와 이름을 입력받으면 tuple로 묶고, 각 입력값의 index를 활용해야 한다고 생각했다.
tuple로 묶어야 나이/이름 2개의 값을 처리하기 더 편하고, 가입한 순서를 추가로 따져야 하므로 index 정보가 필요하기 때문이다.
그 다음 step으로는 {(나이,이름):rank} 의 형태로 처리할까 잠깐 생각했으나, 좋은 옵션이 아니었다.
rank를 구하고 key-value로 묶기 위해서 쓸데없이 복잡해질 수 있었기 때문이다.
그래서 가장 좋은 방법은 tuple로 값을 묶은 후 > sort 라는 내장함수를 사용하는 것이다.
sort를 사용해서 key를 여러개 설정하면, 순서대로 정렬에 적용해준다.
#입력값을 받는다
N = int(input())
profile = []
for i in range(N):
age, name = input().split()
#list에 (나이,이름,인덱스값)을 담는다
profile.append((int(age),name, i))
#정렬 기준: 나이 순, 나이가 같으면 입력 순
profile.sort(key=)여기서 문제는, sort 에 key를 설정해야 한다.
만약 나이만 있다면 바로 reverse 등을 적용할 수 있지만, 현재 profile의 각 요소의 자료구조는 tuple이다.
그리고 다시 tuple 안의 요소들을 key로 설정해야 하는데 각각의 요소들을 구분할 방법이 필요하다.
이 때 lambda 함수를 사용해서 각 요소를 정렬 key로 설정한다.
#입력값을 받는다
N = int(input())
profile = []
for i in range(N):
age, name = input().split()
#list에 (나이,이름,인덱스값)을 담는다
profile.append((int(age),name, i))
#정렬 기준: 나이 순, 나이가 같으면 입력 순
profile.sort(key=lambda x : (x[0], x[2]))
for p in profile:
print(p[0],p[1])안정정렬 vs 불안정 정렬
위 풀이에서, sort를 적용한 부분을 아래와 같이 바꿔도 된다.
#기존 풀이
profile.sort(key=lambda x : (x[0], x[2]))
#변경된 풀이
profile.sort(key=lambda x : (x[0])이는 sort가 안정정렬의 속성을 갖고 있기 때문이다.
안정정렬 (Stable sort)
: "Stable sorting algorithms maintain the relative order of records with equal keys"
: 즉, 복수의 record가 동일한 value 값을 가질 때 원래 순서를 유지한다불안정정렬 (Unstable sort)
: 안정정렬과 달리, 동일한 value 값을 갖는 복수의 record의 원래 순서를 보장해주지 못한다
sort는 안정정렬을 support하기 때문에, 변경된 풀이처럼 x[2] 즉 각 입력값의 index를 기준으로 삼지않아도, 먼저 입력된 순서 = 가입한 순서대로 정렬해주는 것이다. 아래의 예시를 보자.
5, 3, 1, 2, 9, 1*1과 1*은 동일하지만 구분하기 위해 편의상 하나는 별을 붙였다.
안정정렬은 아래를 보장한다.
#안정정렬
1, 1*, 2, 3, 5, 9반면 불안정정렬은 아래 2가지 결과가 나올 수 있다.
#불안정정렬
1, 1*, 2, 3, 5, 9
1*, 1, 2, 3, 5, 9각 속성을 갖는 sorting 은 아래와 같다.
- 안정정렬: bubble sort, insertion sort, merge sort, count sort 등
- 불안정정렬: quick sort, heap sort
문제 출처
백준: https://www.acmicpc.net/problem/10814
참고 자료
https://docs.python.org/ko/3/howto/sorting.html
https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
