백준 1181번 '단어 정렬' 문제를 풀고 기록을 남긴다. 문제 링크
sort()
파이썬에 기본으로 내장된 정렬 함수이다.
시간복잡도는 O(NlogN), 알고리즘은 병합 정렬과 삽입 정렬의 아이디어로 만들었다고 한다.
sort() 함수는 반환값이 없어서, 대상 리스트 원본을 정렬하여 변화시킨다.
L = ['d', 'e', 'a', 'c', 'b']
L.sort() # 리스트 자체를 정렬
print(L)>>> ['a', 'b', 'c', 'd', 'e']sorted()
sort() 와 동일하게 동작하지만,
sorted() 는 반환값이 있어서 새로운 리스트에 assign 시킬 수 있다.
하지만 sort() 와 사용법이 다른 것에 주의해야한다.
L = ['d', 'e', 'a', 'c', 'b']
new_L = sorted(L) # 정렬한 리스트를 반환
print(new_L)>>> ['a', 'b', 'c', 'd', 'e']key
위 사진을 보면 sort() 에는 두 가지 파라미터가 존재한다는 것을 알 수 있는데, key 와 reverse 이다.
key 를 활용하여 정렬에 대한 기준점을 정의할 수 있고,
reverse를 활용하여 리스트를 내림차순으로 정렬할 수 있다.
내림차순 정렬
아래 reverse 예시를 보면 리스트가 내림차순으로 정렬된 것을 볼 수 있다.
L = [-5, 3, -1, 0, 2, -4]
L.sort(reverse=True)
print(L)>>> [3, 2, 0, -1, -4, -5]절댓값 기준으로 정렬
key 를 활용하여 정렬 기준을 재정의 하겠다.
key = abs 로 할당하면 절댓값을 기준으로 정렬한다.
L = [-5, 3, -1, 0, 2, -4]
L.sort(key=abs)
print(L)>>> [0, -1, 2, 3, -4, -5]절댓값 & 내림차순 정렬
위의 두 예시를 동시에 활용할 수 있다.
L = [-5, 3, -1, 0, 2, -4]
L.sort(key=abs, reverse=True)
print(L)>>> [-5, -4, 3, 2, -1, 0]문자열의 길이를 기준으로 정렬
각 문자열의 길이를 기준으로 짧은 순서대로 정렬하려면
key의 기준을 문자열의 길이 즉, key = len으로 할당시켜주면 된다.
L = ["api", "app", "carrier", "demon", "aaa"]
L.sort(key=len)
print(L)>>> ['api', 'app', 'aaa', 'demon', 'carrier']길이를 기준으로 잘 정리되었지만, 뭔가 불편하다. 이유는 뭘까?
사전순(오름차순)으로 정렬이 안되었기 때문이다.
이를 해결하기 위해 우리는 key 값에 lambda 를 사용한다.
lambda
아래와 같이 작성하면 해결된다.
L = ["api", "app", "carrier", "demon", "aaa"]
L.sort(key = lambda x : (len(x), x))
print(L)>>> ['aaa', 'api', 'app', 'demon', 'carrier']위 코드는 첫번째 방법인 len(x)를 통해 길이를 기준으로 정렬하되,
같은 길이가 나오면 두번째 방법인 x를 통해서 사전순(오름차순)으로 정렬하라는 의미이다
문제풀이 예시 코드
위에 설명한 lambda 를 사용하면
백준 1181번 '단어 정렬' 문제를 간단히 풀 수 있다. 문제 링크
N = int(input())
L = []
for i in range(N):
L.append(input())
new_L = list(set(L))
new_L.sort(key = lambda x : (len(x),x))
for i in range(len(new_L)):
print(new_L[i])2차원 배열에서의 사용
위에서 다뤘던 sort와 관련된 모든 내용은 2차원 배열에서도 적용된다.
첫번째 인자 기준 정렬
A = [[2,3],[1,2],[5,1],[2,1],[1,5]]
B = sorted(A, key = lambda x : x[0])
# 첫번째 인자 기준 오름차순 정렬>>> [[1, 2], [1, 5], [2, 3], [2, 1], [5, 1]]
두번째 인자 기준 정렬
A = [[2,3],[1,2],[5,1],[2,1],[1,5]]
C = sorted(A, key = lambda x : (x[0],-x[1]))
#첫번째 인자 기준 오름차순, 두번째 인자는 내림차순 기준 정렬>>> [[1, 5], [1, 2], [2, 3], [2, 1], [5, 1]]
문제풀이 예시 코드
아래 코드는 2차원 배열의 정렬을 사용해서 간단히 풀 수 있는
백준 10814번 '나이순 정렬' 문제의 정답 코드이다. 문제 링크
N = int(input())
member_list = []
for i in range(N):
age, name = input().split()
member_list.append([int(age), name])
member_list.sort(key = lambda x : x[0])
for member in member_list:
print(member[0], member[1])자주 사용되는 코드들
+) 추가로, 코딩테스트에 자주 사용되는 코드들은 아래와 같다.
L.reverse() # L을 거꾸로 뒤집음
L.sort() # L을 오름차순으로 정렬
L.sort(reverse=True) # L을 내림차순으로 정렬
L.sort(key = len) # L을 key 옵션에 따라 정렬
new_L = sorted(L) # sorted 정렬한것을 반환
L.sort(key = lambda x:(len(x),x)) # sort() 사용
new_L = sorted(L, key= lambda x : (len(x), x)) # sorted() 사용
# 첫번째는 길이 오름차순 기준. 길이가 같으면 사전순(아스키코드) 순으로 정렬
