정렬 심화

관련 내용

우리가 2주차에서는 sort() 메소드와 sorted()함수를 배워서 오름차순, 내림차순 정렬을 하는 방법을 배웠습니다.

이번주는 오름차순, 내림차순이 아닌 다양한 기준으로 정렬할 방법에 대해 알아보겠습니다.

보통 이런 문제들은 문제 설명에서 정렬 조건들만 간단하게 적어두면 굉장히 쉬운 문제이기 때문에, 지문 양을 길게 만들어서 정보를 받아들이기 어렵게 만드는 편입니다. 그래서 메모장에 정렬 조건을 잘 정리해서 구현하는 능력이 중요합니다.

익명 함수

먼저 정렬 심화를 공부하기 전에 익명 함수라는 것에 대해 알고 있어야 합니다.

익명 함수는 함수와 다르게 이름이 없습니다. 임의로 이름을 부여할 수는 있지만, 그냥 사용해서는 print(), sorted() 같이 print라는 이름, sorted라는 이름이 없다는 것이죠.

그래서 이런 익명 함수는 주로 한 번 쓰고 버리는 일회용 용도로 사용하는 함수입니다. 여러 번 사용하게 된다면 이름을 붙여서 사용할 수도 있습니다. 그런데 이름을 붙여야 하는 경우에는 보통 함수를 직접 만들어서 사용합니다. (이 부분은 나중에 배우게 됩니다)

익명 함수는 아래와 같이 표현해서 만들 수 있습니다.

lambda파라미터:표현식lambda \: \: 파라미터: 표현식
  • lambda: 익명 함수를 만든다고 선언할 때 쓰이는 키워드입니다.

  • 파라미터(parameter, argument): 함수가 돌아갈 때, 함수 외부에서 가져올 요소입니다. 요소랑 파라미터는 같은 말입니다.

  • 표현식(expression): 이 함수를 통해 어떤 결과 값을 내야 하는지 적는 부분입니다.

lambda x, y : x + y

이런 익명 함수가 있으면 이 함수 밖에 있는 인자를 가져와 x, y 값을 대체해서 x + y를 도출한다는 뜻입니다.

a, b = 2, 3
print((lambda x, y: x + y)(a,b))

위와 같은 상황이면 함수 밖에 있는 인자 a와 b가 각각 x와 y를 대체해서 x + y를 a + b = 5로 도출해낸다는 것이죠.

이런 익명 함수는 임의로 이름을 붙일 수 있습니다. 위에 있는 익명 함수는 요소 2개를 서로 더한 값을 반환하므로 add라는 이름에 저장하겠습니다.

add = lambda x, y : x + y

print(add(1, 2)) # 3
print(add(10, 100)) # 5

# 이 익명 함수는 + 연산자를 지원하는 다른 자료형도 가능
print(add('a', 'bcdefg')) # abcdefg
print(add([1, 2, 3], [4, 5, 6])) # [1, 2, 3, 4, 5, 6]

다른 익명 함수들도 살펴봅시다.

lambda z: z**2
lambda a, b, c: {a, b, c}
lambda a: sum(a) + len(a)

첫 번째 익명 함수는 값을 입력받으면 값의 제곱을 반환하는 익명 함수입니다. ** 연산자를 제공하는 자료형만 가능하겠네요.

두 번째 익명 함수는 3개의 값을 입력받으면 set() 자료형으로 반환하는 익명 함수입니다.

세 번째 익명 함수는 sum()함수와 len()함수를 지원해주는 자료형이 들어가서 (모든 요소의 합)과 (자료형의 길이)를 더한 값을 반환해주는 익명 함수입니다. a에 들어갈 값은 리스트, 튜플, 딕셔너리, 등등 이런 자료형이 될 수 있겠네요.

정렬 심화

잠깐 2주 차에서 배운 내용을 다시 살펴보겠습니다.

우리가 오름차순 정렬을 할 때는 단순히 sort() 메서드와 sorted()함수만 사용하면 됐었습니다.

arr = [4, 117, -40, 5, 20]

arr.sort()
print(arr)
# [-40, 4, 5, 20, 117]
arr = [100, 12, -16, 3**10, 0]

arr = sorted(arr)
print(arr)
# [-16, 0, 12, 100, 59049(3**10)]

내림차순을 할 때는 sort() 메서드와 sorted()함수 안에 reverse = True라고 하거나 [::-1]을 이용하여 내림차순 정렬을 할 수 있었습니다.

arr = [1, 3, 2, 5, 4]

arr.sort(reverse = True)
print(arr)
# [5, 4, 3, 2, 1]

arr.sort()
print(arr[::-1])
arr = [2, 38, 5, 1, -0]

arr = sorted(arr, reverse = True)
print(arr)
# [38, 5, 2, 1, 0]


arr = sorted(arr)[::-1]
print(arr)

arr = sorted(arr)
print(arr[::-1])

내림차순에서는 reverse라는 인자를 sort() 메서드나 sorted() 함수에 넣었는데요. 다양한 기준으로 정렬하려면 이런 reverse 인자와 비슷하게 key라는 인자를 필요로 합니다.

arr= [ blah blah ]

arr = sorted(arr, key = blah blah)

arr.sort(key = blah blah)

print(arr)

우리가 위에서 배운 익명 함수가 바로 key에 들어갈 값입니다.

1개의 기준으로 정렬하기

key인자는 아래와 같이 사용하시면 됩니다. 여기서 변수는 넣고 싶은 변수 명을 지어서 넣으면 됩니다. 저 같은 경우에는 대충 a나 x라고 값을 넣는 편입니다.

arr = [ 리스트값 ]

arr.sort(key = lambda 변수: 정렬 조건)

arr = sorted(arr, key = lambda 변수: 정렬 조건)

print(arr)

일단 먼저 알고 계셔야 할 것은 우리가 기본으로 사용하는 오름차순을 key를 이용하여 만든다면 정렬 조건에 변수만 그대로 적으면 됩니다.

변수를 x로 둔다면 정렬 조건에서 x라고 적으면 됩니다.

arr = [100, 1, 5, 40]

arr.sort(key = lambda x: x)
print(arr)

arr = sorted(arr, key = lambda x: x)
print(arr)

# [1, 5, 40, 100]

여기서 내림차순으로 정렬한다면 reverse=True를 사용하면 됩니다.

그리고 이런 단순 오름차순 정렬은 사전 순으로 정리한다고 말하고 있습니다.

이번엔 문자열 값들이 들어가 있는 리스트가 있을 때, 단어의 길이를 기준으로 정렬하는 코드를 짜봅시다.

arr = ['a', 'cdef', 'abcd', 'bcd', 'z']

위와 같은 문자열 값이 5개 들어간 리스트를 정렬해 봅시다.

단어의 길이를 기준으로 정렬하려면 key = 변수 : 정렬 조건에서 변수는 아무 이름이나 쓰면 되니까 x라고 하고, 정렬 조건은 단어의 길이를 기준으로 정렬하므로 len(x)를 사용하면 되겠습니다.

arr = ['a', 'cdef', 'abcd', 'bcd', 'z']

arr.sort(key = lambda x: len(x))
print(arr)
# ['a', 'z', 'bcd', 'abcd', 'cdef']

arr = sorted(arr, key = lambda x: len(x))
print(arr)

이러면 변수의 길이를 기준으로 정렬을 하게 됩니다. 작동 과정을 생각해보면 아래와 같습니다.

# 원래 상태
['a', 'cdef', 'abcd', 'bcd', 'z']

# len(x) 적용
[ 1('a'), 4('cdef'), 4('abcd'), 3('bcd'), 1('z')]

# len(x) 기준으로 정렬
[ 1('a'), 1('z'), 3('bcd'), 4('cdef'), 4('abcd')]

여기서 궁금한 점이 하나 생깁니다. 위와 같이 길이가 1인 문자열과 길이가 4인 문자열은 동점자가 있는데 어떤 기준으로 정렬을 할까요?

이런 경우에는 단순하게 배열의 index가 빠른 순서로 정렬을 하게 됩니다. 'a'의 인덱스는 0, 'z'의 인덱스는 4이므로 'a'가 'z'보다 앞에 있게 되고, 'cdef'의 인덱스는 1, 'abcd'의 인덱스는 2이므로 'cdef'가 'abcd'가 앞에 나오게 됩니다.

다른 예제를 살펴봅시다.

만약 정수 범위의 값이 저장된 배열이 있는데 이것을 절댓값으로 바꾼 값을 기준으로 내림차순 정렬을 해본다고 가정해봅시다.

arr = [50, -100, -50, -3, 0 , 10, 20, 50, 50]

key = lambda 변수 : 정렬 조건이므로 변수는 아무 변수명이나 상관없으니 a라고 적고, 정렬 조건은 절댓값이므로 abs(a)를 입력하면 됩니다.

내림차순 정렬이므로 [::-1]을 사용하거나 reverse = True를 사용하시면 됩니다.

arr = [50, -100, -50, -3, 0, 20, 50, 50]

arr.sort(key=lambda a: abs(a), reverse=True)
print(arr)

arr = sorted(arr, key=lambda a: abs(a), reverse=True)
print(arr)

# [-100, 50, -50, 50, 50, 20, -3, 0]

작동 과정은 아래와 같습니다.

# 기본값
[50, -100, -50, -3, 0, 20, 50, 50]

# abs()함수를 통해 절댓값을 기준으로 정렬
[0(0), 3(-3), 20(20), 50(50), 50(-50), 50(50), 50(50), 100(-100)]

# reverse = True이므로 절댓값을 기준으로 내림차순 정렬
[100(-100), 50(50), 50(-50), 50(50), 50(50), 20(20), 3(-3), 0(0)]

여기서는 절댓값이 50인 값이 4개나 있습니다. 그런데 reverse = True를 하면 index가 0(50), 2(-50), 6(50), 7(50)이므로 거꾸로 7(50), 6(50), 2(-50), 0(50)일 것 같으나, 마찬가지로 이것도 먼저 배열에 나온 순서대로 값이 나오게 됩니다.

여러 개의 기준으로 정렬하기

이번엔 정렬 조건이 여러 개일 때의 정렬을 배워봅시다.

조건이 여러 개면 간단하게 익명 함수의 표현식(expression)에서 리스트나 튜플 같은 자료형 안에 값을 넣어서 여러 가지 조건에 의해 값들을 정렬할 수 있게 됩니다.

lambda변수:[1순위조건,2순위조건,....]lambda\:변수: [\:1순위\:조건,\:2순위\:조건,\:....\:]

문자열 값들이 들어 있는 리스트가 있을 때, 이 리스트를 1순위로 단어의 길이의 역순, 2순위로 첫 글자의 아스키 코드를 기준으로 정렬을 해본다고 가정해봅시다.

arr = ['a', 'CdeF', 'ABcd', 'Bcd', 'z']

이렇게 대소문자가 섞여있는 리스트라고 해봅시다.

익명 함수에 사용하는 변수는 s라고 대충 정하고, 조건을 만들어봅시다.

1순위는 단어의 길이의 역순이므로 -len(s)입니다.

2순위는 첫 글자의 아스키 코드 기준이므로 ord(s[0])입니다.

이것을 코드로 짜본다면 아래와 같습니다.

arr = ['a', 'CdeF', 'ABcd', 'Bcd', 'z']

arr = sorted(arr, key = lambda s: [-len(s), ord(s[0])])
print(arr)

arr.sort(key = lambda s: [-len(s), ord(s[0])])
print(arr)

#['ABcd', 'CdeF', 'Bcd', 'a', 'z']

이번엔 리스트 안에 리스트들이 있는 2차원 리스트를 정렬하는 방법도 알아봅시다.

학원에서 시험을 봤는데 아래와 같은 리스트가 있다고 해봅시다. 리스트 하나에는 [이름(문자열), 나이(int형), 성적(float)]의 값을 가지고 있습니다.

arr = [['김씨', 13, 4.0], ['이씨', 15, 3.0], ['최씨', 13, 3.0],
        ['박씨', 14, 4.0], ['정씨', 14, 3.0], ['조씨', 15, 3.0]]

학원에서는 이 리스트를 정렬해서 모든 학생의 성적을 공개하는 일을 하려고 하는데, 정렬 조건은 먼저 나이순으로 오름차순 정렬, 나이가 같다면 성적순으로 내림차순 정렬, 성적마저도 같다면 이름을 사전 순서대로 정렬한다고 합니다.

이것도 마찬가지로 lambda 변수 : [1순위 조건, 2순위 조건, ... ]를 이용하면 됩니다.

변수 이름은 student를 줄여서 studt라고 해봅시다.

1순위는 나이순으로 오름차순 정렬을 하므로 studt[1]입니다.

2순위는 성적순으로 내림차순 정렬을 하므로 -studt[2]입니다.

3순위는 이름을 사전 순서대로 정렬하므로 studt[0]입니다.

따라서 아래와 같이 코드를 정렬할 수 있습니다.

arr = [['김씨', 13, 4.0], ['이씨', 15, 3.0], ['최씨', 13, 3.0],
        ['박씨', 14, 4.0], ['정씨', 14, 3.0], ['조씨', 15, 3.0]]

arr = sorted(arr, key=lambda studt:[studt[1], -studt[2], studt[0]])
print(arr)

arr.sort(key = lambda studt: [studt[1], -studt[2], studt[0]])
print(arr)

#[['김씨', 13, 4.0], ['최씨', 13, 3.0], ['박씨', 14, 4.0],
# ['정씨', 14, 3.0], ['이씨', 15, 3.0], ['조씨', 15, 3.0]]

참고로 정렬 조건에는 필요하다면 함수를 따로 만들어서 문제에서 요구하는 값을 적절히 숫자로 수치화해서 값을 반환해준 다음, 그 반환 값으로 정렬을 할 수도 있습니다.

예시를 들어보자면 문자열만 들어가 있는 리스트가 있을 때, 첫 글자의 아스키 코드에 의해 오름차순 정렬을 해봅시다. 이때 아스키 코드를 반환하는 함수를 만들어서 사용하겠습니다.

def ascii(x):
    reutrn ord(x[0])

arr = ['abc', 'bear', 'a', 'abcde', 'bear', 'cup']

arr = sorted(arr, key=lambda a: ascii(a))
print(arr)

arr.sort(key=lambda a: ascii(a))
print(arr)

# ['abc', 'a', 'abcde', 'bear', 'bear', 'cup']

이런 방법도 있지만 우리는 아직 함수를 배우지 않았기 때문에 따로 함수를 만들어서 푸는 문제들을 풀지는 않을것 입니다.

나중에 함수를 배우게 된다면 복습 문제에 넣을 수는 있겠네요.

이제 문제를 풀어봅시다.

연습 문제

BOJ 1181

1순위: 길이가 짧은 것부터

2순위: 사전 순서대로

주의할 점은 출력할 때 같은 단어는 한 번만 입력하라고 합니다. 이 부분은 set을 이용해 만들 수 있겠네요.

일단 입력값을 받는 코드를 짜봅시다.

n = int(input())
arr = []

for i in range(n):
    arr.append(input())

그리고 중복 제거를 해줘야 하므로 set()를 이용해 세트로 바꿔주고 다시 list()를 이용하여 리스트로 꿔줍시다.

n = int(input())
arr = []

for i in range(n):
    arr.append(input())

arr = list(set(arr))

이제 이 리스트를 정렬해주면 됩니다. 익명 함수 변수를 x라고 두면 [len(x), x]라고 두면 되겠네요.

n = int(input())
arr = []

for i in range(n):
    arr.append(input())

arr = list(set(arr))

arr.sort(key=lambda x: [len(x), x])
print('\n'.join(arr))

BOJ 10825

이 문제도 조건이 바로 나와 있습니다. 이번엔 좀 까다롭네요.

  1. 국어 점수가 감소하는 순서로

  2. 국어 점수가 같으면 영어 점수가 증가하는 순서로

  3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로

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

입력 값은 이름, 국어, 영어, 수학 점수가 주어진다고 합니다. 일단 입력값을 받아봅시다.

n = int(input())
arr = []
for i in range(n):
    name, a, b, c = input().split()
    arr.append([name, int(a), int(b), int(c)])

이제 정렬 조건을 따져봅시다. 변수는 x라고 두겠습니다.

1순위: 국어 점수 감소하는 순서(내림차순) -> -x[1]

2순위: 영어 점수가 증가하는 순서(오름차순) -> x[2]

3순위: 수학 점수가 감소하는 순서 -> -x[3]

4순위: 이름을 사전 순으로 -> x[0]

이제 이것을 코드로 짜면 됩니다. 문제 1181에서는 sort()를 썼으니 이번엔 sorted()를 사용하겠습니다.

n = int(input())
arr = []
for i in range(n):
    name, a, b, c = input().split()
    arr.append([name, int(a), int(b), int(c)])

arr = sorted(arr, key=lambda x: [-x[1], x[2], -x[3], x[0]])

이제 출력을 하면 됩니다. 마찬가지로 문제 1181에서는 join을 사용했으니 이번엔 for문을 사용하겠습니다.

n = int(input())
arr = []
for i in range(n):
    name, a, b, c = input().split()
    arr.append([name, int(a), int(b), int(c)])

arr = sorted(arr, key=lambda x: [-x[1], x[2], -x[3], x[0]])

for i in range(n):
    print(arr[i][0])

이렇게 해서 우리는 여러 가지 조건에 의해 정렬을 어떻게 하는지 알게 되었습니다. 이런 문제 유형은 코딩 테스트 1차, 대회 예선에서 은근히 출제되는 중요한 유형이니까 잘 공부하시길 바랍니다.

이번 주는 마지막 파트에 문제가 없으므로 총 6문제를 배정했습니다.

풀어볼 문제

Last updated