코딩테스트에서 사용할만한 정렬기법

정렬 기술

📌sort 메서드

오름 차순 정렬

리스트에는 기본 내장된 sort 메서드가 존재한다.

이를 사용하면 쉽게 정렬이 가능하다.

list1 = [7,1,5,3,2,4,6]
list1.sort()
print(list1) # [1, 2, 3, 4, 5, 6, 7]

내림 차순 정렬

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

📌특정 조건으로 정렬하기

단순한 크기순 정렬이 아니라 특정 조건으로 정렬하려면 어떻게 해야 할까?

예를 들어 딕셔너리 경우 key와 value로 자료형이 구성되어 있다.

그 중 value로 정렬하려면 다음과 같은 방법을 이용할 수 있다.

1. 정렬의 기준이 되는 함수를 정의한다.
2. 정의한 함수를 sort 메서드의 파라미터로 전달한다.

1. value 기준 정렬

오름 차순 정렬하기

list1 = [('Geehoon', 173), ('Songhye', 165), ('Taehoon', 180)]

# 정렬의 기준이 되는 함수 정의
def pivot(x):
    return x[1] # 딕셔너리의 value를 리턴
list1.sort(key=pivot)
print(list1) # [('Songhye', 165), ('Geehoon', 173), ('Taehoon', 180)]

내림 차순 정렬 하기

list1 = [('Geehoon', 173), ('Songhye', 165), ('Taehoon', 180)]

# 정렬의 기준이 되는 함수 정의
def pivot(x):
    return x[1] # 딕셔너리의 value를 리턴
list1.sort(key=pivot, reverse=True)
print(list1) # [('Taehoon', 180), ('Geehoon', 173), ('Songhye', 165)]

2. key 기준 정렬

이 경우 이름순으로 정렬된다.

list1 = [('Geehoon', 173), ('Songhye', 165), ('Taehoon', 180)]

# 정렬의 기준이 되는 함수 정의
def pivot(x):
    return x[0] # 딕셔너리의 key를 리턴
list1.sort(key=pivot) # 이름순(알파벳순)으로 정렬이 일어난다.
print(list1) # [('Geehoon', 173), ('Songhye', 165), ('Taehoon', 180)]

3. Lambda 사용하기

이를 사용하는 응용 문제로 백준 1181번 단어를 정렬하는 문제가 있다.

위 문제 풀이 과정은 3단계로 이루어진다.

1. set을 활용해 중복된 단어 제거
2. 단어의 길이순으로 오름차순 정렬
3. 단어의 길이가 같은 경우 알파벳순 오름차순 정렬

따라서 sorting을 적용할 때 단어의 길이, 그리고 단어라는 2가지 기준이 적용되어야 한다.

import sys

n = int(sys.stdin.readline())
words = [sys.stdin.readline().strip() for i in range(n)]

def solution(words):
    result = list(set(words))
    result.sort(key = lambda word : (len(word), word))
    return result

result = solution(words)
for answer in result:
    print(answer)

위와 같이 lambda 식을 사용해 len과 word 2가지를 key로 넘겨주었다.

result의 단어를 하나씩 꺼내서 (len(), word)를 튜플로 구하고 정렬 기준으로 전달했다.

📌sorted 메서드란?

사본도 정렬이 될까?

sort() 메서드는 리스트 복사후 정렬 시 원본과 사본 모두 정렬된다.

반면 sorted()는 정렬 후 다시 원본에 대입해주어야만 정렬된 상태가 반영된다.

sort 메서드

list1 = [5,1,3,2,4]
list2 = list1
list1.sort()
# list2도 정렬이 되었을까?
print(list1) # [1,2,3,4,5]
print(list2) # [1,2,3,4,5]

sort 메서드는 사본까지 정렬이 된다.

그 이유는 단순 복사를 할 경우 얕은 복사가 일어나기 때문이다.

따라서 원본과 사본이 하나의 리스트 객체를 공유하게 된다.

여기서는 [5,1,3,2,4]를 list1과 list2가 같이 참조하고 있다.

따라서 둘 중 하나만 정렬하면 당연히 모두 정렬된 상태가 반영된다.

sorted 메서드

sorted 메서드는 원본은 바꾸지 않고 정렬할 수 있다.

list1 = [5,1,3,2,4]
print(sorted(list1)) # [1,2,3,4,5]
print(list1) # [5,1,3,2,4]

따라서 원본을 그대로 두고 사본만 정렬해서 사용할 수 있다.

list1 = [5,1,3,2,4]
list2 = sorted(list1)
print(list1) # [5,1,3,2,4]
print(list2) # [1,2,3,4,5]