sort()와 sorted()를 활용하여 코딩테스트 문제를 해결해보자!

• 문자열의 정렬을 활용한 전화번호 목록 문제
• 숫자의 정렬을 활용한 귤 고르기 문제

파이썬에서의 정렬

파이썬의 리스트가 가진 메서드 중 sort()가 있다. 리스트 내부의 값을 오름차순 혹은 내림차순으로 정렬 해준다. sorted() 또한 같은 기능을 한다.

sort()와 sorted()의 차이는 sort()는 원본 값을 변경하고 sorted()는 변경하지 않는다.

sort()란?

a_list = [100, 3, 20, 5]

print(a_list.sort()) # None
print(a_list) 		 # [3, 5, 20, 100]

sort()는 리스트의 메서드이다. 리스트 객체에만 사용할 수 있으며, 반환 값이 없다.

메모리 상에서 해당 객체의 값을 변경하므로 a_list를 출력했을 때 바뀐(정렬된) 값이 나온다.

sorted()란?

b_list = [100, 3, 20, 5]

print(sorted(b_list)) # [3, 5, 20, 100]
print(b_list) # [100, 3, 20, 5]

b_list = sorted(b_list)
print(b_list) # [3, 5, 20, 100]

sorted()는 파이썬의 내장함수이다. 리스트에서만 사용 가능한 sort()와는 다르게 튜플 등 반복 가능한 객체(Iterable)에서 사용이 가능하다.

_튜플_과 _딕셔너리_ 예제를 통해 두 메서드(함수)의 **차이**를 확인해보자.

mytuple = (1,4,5,2,3)
mydict = {"a":1,"b":2}

mytuple.sort() 
  # AttributeError: 'tuple' object has no attribute 'sort'
mydict.sort() 
  # AttributeError: 'dict' object has no attribute 'sort'

sort()는 튜플과 딕셔너리를 정렬할 수 없다.

sorted(mytuple) # [1, 2, 3, 4, 5]
sorted(mydict) # ['a', 'b']

반면, sorted()는 가능하다.

---

정렬 메서드의 동작 원리

지금까지 오름차순 혹은 내림차순의 정렬은 숫자로만 했었다. 문자의 정렬 또한 가능하다는 것을 알고 있었지만 정확하게 어떤 단계로 정렬되는지 모르고 있었다.

해시 알고리즘에 해당하는 전화번호 목록 문제에서 문자열 정렬을 위해 sort()를 활용하였다. 그 과정에서 sort()가 문자열을 어떤 방식으로 정렬하는 지 알 필요가 있었다.

숫자의 정렬

숫자의 정렬은 숫자 간의 크고 작음을 비교하여 나열하는 것이다. 숫자 리스트를 오름차순 혹은 내림차순으로sort()한다면 우리는 그 결과를 한 눈에 이해할 수 있다.

num_list = [4, 5, 12, 1, 8, 0]
num_list.sort() # [0, 1, 4, 5, 8, 12]

숫자를 sort()하는 경우 정수값의 크기를 비교하여 정렬된다. 물론 num_list 내부의 정수값은 메모리에는 이진법으로 변환된 상태로 저장되어 있을 것이다.

문자열의 정렬

문자(열)의 경우는 유니코드나 아스키 코드로 변환된 값을 비교한다. (Python3은 유니코드 사용) 유니코드나 아스키코드 또한 숫자의 정렬처럼 크기 비교시 컴퓨터 내부적으로는 변환된 정수값을 비교한다.

아래와 같은 **문자열**이 저장된 리스트를 정렬했을 때, 왜 다음과 같은 결과가 나오는지 이해해보자.

str_list = ["123","1234","3","124"]
str_list.sort() # ['123', '1234', '124', '3']

파이썬의 내장 함수 `ord()`는 **문자**에 대한 **유니코드** 코드 포인트(정수)를 반환한다.

문자열에는 사용할 수 없으므로 반복문을 활용하여 문자열에서 문자를 하나씩 추출 후 유니코드로 변환하여 딕셔너리의 값으로 저장하였다.
(참고로 아스키코드 값은 유니코드에 그대로 유지된다.)

str_list = ["123","1234","3","124"]

uni_dict = {s: [str(ord(c)) for c in s] for s in str_list}
# {'123': ['49', '50', '51'],
  '1234': ['49', '50', '51', '52'],
  '3'   : ['51'],
  '124' : ['49', '50', '52']}


# 유니코드 값을 기준으로 오름차순 정렬
sorted(uni_dict.items(), key=lambda x: x[1])
# [('123' , ['49', '50', '51']),
   ('1234', ['49', '50', '51', '52']),
   ('124' , ['49', '50', '52']),
   ('3'   , ['51'])]


# 유니코드 값을 기준으로 오름차순 정렬
sorted(uni_dict.items())
# [('123' , ['49', '50', '51']),
   ('1234', ['49', '50', '51', '52']),
   ('124' , ['49', '50', '52']),
   ('3'   , ['51'])]

동일하게 ['123', '1234', '124', '3'] 순으로 정렬되었다. 문자열은 해당 유니코드 값을 왼쪽부터 하나씩 사전순으로 크기를 비교하는 것을 알 수 있다.

4개의 문자열의 첫째 자리는 49와 51이 있다. 따라서 51을 가진 '3'이 가장 큰 값이 된다. 같은 과정으로 둘째자리도 비교한다. 셋째 자리는 51과 52가 있어 52를 가진 '124'가 '3'다음으로 크다.

결론적으로 숫자나 문자 모두 내부적으로는 정수를 비교하여 정렬된다는 것을 알 수 있다.

---

문제

1. 전화번호 목록

• 문자열의 정렬을 활용한 전화번호 목록

phone_book 리스트에 정수로 이루어진 문자열이 저장되어 있다. 한 문자열이 다른 문자열의 접두어인지를 찾는 문제다. 예를 들면, "111"은 "1110000"의 접두어다. "1100"은 "1110"의 접두어가 아니다.

해결 과정

리스트에 숫자가 문자열로 저장되어 있으므로 숫자의 정렬이 아닌 문자열의 정렬을 이용해야 했다.

파이썬의 정렬 메서드 sort()를 활용하여 전화번호 목록 문제를 해결하는 코드를 아래와 같이 작성했다.

def solution(phone_book):

    phone_book.sort() # 리스트 내 문자열의 정렬
    
    for i in range(len(phone_book)-1):
    	# 정렬된 상태에서 인접한 요소의 접두어를 비교
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return True

접두어를 비교하는 문제이므로 리스트 내의 문자열을 정렬하면 왼쪽부터 같은 문자를 가진 문자열이 인접하여 나열될 것이다. 따라서 리스트 내의 요소를 비교할 때 그나마 빠르게 False를 반환할 수 있다.

---

2. 귤 고르기

• 숫자의 정렬을 활용한 귤 고르기

tangerine 리스트에 자연수가 저장되어 있다. 해당 숫자는 귤의 크기를 뜻하며 해당 크기를 가진 귤은 여러개 존재할 수 있으므로 저장된 자연수는 중복될 수 있다. 크기가 다르면 종류가 다르므로 갯수 k가 주어질 때 종류의 최솟값을 구해야 한다.

해결 과정

종류는 중복될 수 있고 갯수를 구분해야 하므로 딕셔너리를 활용하기로 했다. 요소의 갯수를 세어 값으로 저장하기 위해 컬렉션 모듈의 Counter를 사용하였다. (Counter에 관한 내용은 여기서 확인)

from collections import Counter

def solution(k, tangerine):
	# 내림차순 정렬 {"크기(종류)":"갯수"}
    tan_list = sorted(Counter(tangerine).items(), key=lambda x : x[1], reverse=True)
    for i, t in enumerate(tan_list):
        k -= t[1]
        if k <= 0: 
            return i+1

tan_list에서 키는 종류를, 값은 갯수를 나타낸다.

그후 해당 딕셔너리를 값 기준으로 내림차순 정렬했는데, 값이 개수이므로 큰 갯수를 먼저 확인하면 k에 맞는 최솟값을 구할 수 있다.

sorted()의 정렬 기준 설정

sorted()는 다음과 같이 정렬의 기준을 설정할 수 있다.

# sorted(정렬 대상, key=정렬 기준, reverse=오름차순/내림차순)

sorted(Counter(tangerine).items(), key=lambda x : x[1], reverse=True)

문제를 해결하는 코드에서는 정렬 기준을 설정할 때 lambda를 사용하여 전달받은 값의 1번째 인덱스 값 lambda x : x[1]을 key로 두었다.

정렬 대상의 내부 값이 리스트 혹은 딕셔너리이고 특정 값에 접근하여, 그 값을 기준으로로 정렬하는 경우에는 lambda를 유용하게 사용할 수 있다.

---

Reference

Sorting Techniques