Python으로 알고리즘 문제 쉽게 풀기 (3) - 기초 정렬을 이용한 잡기술

자 오늘을 마지막으로... 하려고 했는데 생각보다 길어져서 다시 나누게 되었습니다.

생각 날때마다, 여러가지 잡기술들을 모아서 알려드리도록 할께요.

오늘은 python에서 기본적으로 제공해주는 정렬을 활용해서 조금이라도 코드를 편하고, 가독성있게 (나에게만 일지도...) 짤 수 있는 비법들을 알려드리도록 하겠습니다.

오늘 배울 내용들을 간단히 나열해드리자면,

• sort, sorted 함수
• enumerate 함수
• for문에서 이름으로 원소 꺼내오기
• 이들을 활용한 정렬처리 잡기 술

입니다.

정렬 트릭

정렬은 문제를 풀때 굉장히 자주 사용하게 되는 라이브러리입니다.

단순히 오름차순으로 정렬할 때 python에서 제공하는 sorted 라이브러리나 sort라이브러리를 사용합니다. 간단한 정렬 문제를 해보도록 할께요.

정렬 기초

이번에 풀어볼 문제는 수 정렬하기 입니다.

https://www.acmicpc.net/problem/2750

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

5 5 2 3 4 1

예제 출력

1 2 3 4 5

문제가 간단해서 좋군요. 뭐가 문제겠어요? 정렬을 알아보는 가벼운 예제니까 빠르게 후딱처리하고 넘어갑시다.

사실 이 문제는 2가지 해법이 있어요. 크게 어려운 해법은 아니고, 원본 배열을 건드리냐 안건드리냐에 따라서 달라지게 되죠. 일단 먼저 보실까요?

답 코드1 - sorted

N = int(input())
D = [int(input()) for i in range(N)]
sorted_D = sorted(D)
for num in sorted_D:
    print(num)

답 코드2 - sort

N = int(input())
D = [int(input()) for i in range(N)]
D.sort()
for num in D:
    print(num)

sorted는 D를 건드리지 않고 새롭게 정렬된 배열을 return합니다.

그에 비해서 sort는 D의 배열 자체를 정렬된 상태로 바꿔버리죠.

이정도면 기본은 되었습니다. 이제 트릭을 알아보러 가시죠.

복잡한 정렬 수행하기

기본적으로 제공되는 함수는 여러가지 조건으로 복잡한 정렬을 수행하기위해서는 비교하기 위한 함수를 넘겨줘야하는 불편한 점이 있죠.

특히 많은 문제에서 여러가지 조건에 따라 비교를 수행해야하는 경우가 왕왕있습니다.

알고리즘은 정확하게 짜는 것도 중요하지만, 빠르게 짜는게 중요한 역할을 합니다. 그때 복잡한 비교구문을 일일이 작성해서 정렬하는 것은 시간낭비입니다.

빠르게 정렬하기 위한 꿀팁을 알려드릴께요. 바로 python 내장 정렬을 이용하는 방법입니다.

python 내장정렬은 다음과 같은 특징을 가지고 있습니다.

1. 정렬은 오름차순으로 수행한다. (위의 예제에서 보여드렸죠?)
2. 만약 정렬의 내용물이 tuple이라면 tuple의 낮은 인덱스에 있는 원소를 기준으로 정렬한다.

2번 항목이 잘 이해가지 않으실꺼에요. 간단한 예제를 드릴께요.

a = [
    (2, 4),
    (2, 3),
    (1, 4),
    (1, 3),
]
a.sort()

print(a)

이 코드의 출력은 무엇일까요? 바로

[(1, 3), (1, 4), (2, 3), (2, 4)]

가 됩니다.

첫번 째 원소 1과 2를 비교해서 오름차순으로 정렬을 수행하죠.

만약 첫번째 원소가 같다면 두번째 원소 3과 4를 비교해서 오름차순으로 정렬을 수행합니다.

직관적으로 당연히 그렇게 되어야 맞겠죠?

바로 이 트릭을 이용해서 복잡한 정렬을 추가적인 함수를 작성하지 않고 수행할 수 있습니다.

바로 문제로 가실께요.

https://www.acmicpc.net/problem/1181

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력

13 but i wont hesitate no more no more it cannot wait im yours

예제 출력

i im it no but more wait wont yours cannot hesitate

자 다소 복잡하죠? 하지만 코드는 문제보다 짧고, 쉽습니다.

바로 보시면서 이해하시죠.

정답 코드

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

1~2: 첫 두줄은 늘상 같은 인풋받는 방식입니다.

3~3: 중복을 없애주기 위해서 set 함수를 사용합니다.

4~5: 이게 바로 제가 말하고자하는 정렬트릭입니다.

python의 정렬은 첫번째 것을 먼저 정렬하고, 그다음 우선순위를 두번째 원소로 둡니다.

따라서 정렬의 첫번째 조건을 첫번째 원소에 두번째 조건을 두번째 원소에 넣는 방식으로 넣어두고 정렬을 할 수 있습니다.

만약 길이가 긴 것순으로 정렬하라고 했다면 어떻게 하면 될까요?

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(-len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

라고 하시면 됩니다.

이처럼 오름차순, 내림차순도 안에 넣는 원소를 바꾸기만 해서 구현해낼 수 있습니다.

기본정렬에서 추가적인 함수를 호출하지 않고도 처리할 수있어요.

자잘한 꿀팁

사실 이보다 간단하게 처리할 수 있어요.

list뿐 아니라 set도 list처럼 입력을 받으면서 초기화할 수 있습니다.

N = int(input())
D = {input() for i in range(N)}
D = sorted([(len(s), s) for s in D])

for l, s in D:
    print(s)

당연히 더 줄일수도 있죠.

하지만 이 이상부터는 숏코딩의 영역입니다.

착한 어른이들은 따라하지 마세요!

정렬 트릭의 활용

https://www.acmicpc.net/problem/10814

눈에 보이는 조건들만이 조건이 아닙니다. 들어온 순서나, 길이, 입력받은 상수값 같은 것들도 이에 활용할 수 있습니다. 위 문제에도 이를 활용할 수 있습니다.

문제 설명은 지면이 길어져서 생략하도록 할게요.

입력 예제 1

3 21 Junkyu 21 Dohyun 20 Sunyoung

정답 코드

N = int(input())
D = [input().split(" ") for i in range(N)]
D = sorted([(int(age), order, name) for order, (age, name) in enumerate(D)])

for age, order, name in D:
    print(age, name)

이 코드에도 몇가지 보여드릴께 있습니다. 이 코드에서 배울 것은 크게 3가지입니다.

1. enumerate
2. for문의 unpack 트릭
3. order를 정렬의 조건으로 넣기

enumerate

enumerate는 반복문을 돌 때, 배열의 인덱스, 배열의 원소 두가지를 활용할 수 있게 해줍니다.

3개라구요? 아닙니다 잘 보세요! 2개입니다.

order, (age, name) 2개라구요.

for문에서 이름 붙여서 가져오기

이것이 바로 python에서 for문에서 container를 unpack할 시에 제공하는 문법입니다.

아마 컨테이너 안에 있는 tuple에서 몇가지 원소를 이름을 붙여서 가져올 때 사용해보셨을 텐데, 컨테이너 안에 컨테이너에서 이름을 붙여서 가져올 수 있다는 사실은 사람들이 잘 모르시는 경우가 많았습니다.

이 경우에는 괄호를 생략하실수 없습니다! 바로 container에서 가져옴과 동시에 이름을 붙일 수 있기 때문에 코드의 가독성이 더 올라가게 되죠.

순서를 정렬의 기준으로 만들기

enumerate에서 가져온 배열의 인덱스는 곧 input을 받은 순서입니다. 문제의 조건에서

1. 나이
2. 들어온 순서 (가입한 순서)

라고 했기 때문에 (int(age), order) 순으로 만든 것이죠.

엇 그런데 name이 추가로 들어가 있네요?

맞습니다. 실제로 출력을 할 때에는 이름 정보가 필요합니다.

정렬시에 사용하기위해서가 아니라 그 데이터 자체를 보존하기 위해서 넣어 준거에요.

연습 문제

https://www.acmicpc.net/problem/10825

마무리

사실 오늘로 끝내려고 했는데, 정렬처리 잡기술이 조금 주저리 주저리가 길어졌네요.

다음에 시간이되면 다른 잡기술들도 소개하도록 하겠습니다.

생각보다 제가 사용하는 잡기술들이 많네요...

graph 알고리즘에서 사용하는 것들도 많고, 슬라이싱을 이용한 잡기술들도 굉장히 많은데

흠... 언제 다쓰지 이거