python3으로 알고리즘 풀 때 팁 정리

정렬을 유용하게 사용하자

백준 그룹 단어 체커 1316문제를 풀다가 아주 짧은 코드로 푼 사람이 있어 살펴보았더니 정렬을 사용하는 신박한 방법을 발견했다. 우선 나의 풀이방법은 이미 나왔던 단어들을 history라는 변수에 배열로 저장하고, 입력 받은 변수의 character가 history에 존재한다면 그룹 단어가 아닌 것으로 간주하는 방법을 사용했다. 그러나 정렬을 사용하면 아주 쉽게 풀이가 가능했다. 핵심은 key를 조작하는 것이었다.

res = 0
for i in range(int(input())):
    s = input()
    if list(s) == sorted(s, key=s.find):
        res += 1
print(res)

s가 ‘wordo’라는 문자열 이라고 했을 때 list(s) 의 결과 값은

['w','o','r','d','o']

이다.

그리고 일반 적으로 sorted(s)를 하면 결과 값은 사전 순으로 정렬 되기 때문에

['d','o','o,','r','w']

이다. 여기서 sorted함수에 key값으로 익명 함수 lamda를 적용하면 lamda함수의 리턴 값에 맞게 정렬 순서를 조작 할 수 있다. 위의 예에서는 ‘wordo’ 스트링의 find함수를 lamda함수에 넘겨주었다. find 함수는 string을 인자로 받는데 sorted에서 lamda로 넘겨준 함수에 정렬 될 배열의 요소 하나하나가 인자로 넘어간다. 먼저 처음 문자인 w가 넘어가면 find 함수는 첫 w의 위치인 0 을 반환한다. 따라서 w의 위치는 맨 처음 0 이 될 것이다. 두 번째로 ‘o’가 인자로 넘어가면 ‘wordo’에서 첫 ‘o’의 위치인 1이 반환 되므로 두 번째 ‘o’의 위치는 1이다. 이렇게 ‘r’과 ‘d’마찬가지로 적용 되는데, 마지막에 ‘o’가 다시 한번 나타난다. 이 ‘o’가 ‘word’.find(‘o’)와 같이 인수로 넘어간다면 처음 o의 위치인 1을 반환하게 되어 1의 위치에 있는 ‘o’를 밀어내고 그자리에 앉게 된다. 결국 wordo와 배열이 달라지므로 앞에 있던 단어를 반복 한 것이 됨으로 결과는 그룹 단어가 아닌 것이다.

정확히 기억은 잘 나진 안지만 가끔씩 배열을 정렬 하고 생각해보면 쉽게 풀렸던 문제들이 몇몇 있었다. 시간이 오래 걸리는 것도 아니니 정렬을 한 다면 풀이가 어떻게 될지 생각해보는 것도 나쁘지 않은 것 같다.

combinations

백준 2309번 (일곱 난쟁이)는 9명의 난쟁이 후보중에서 2명의 가짜 난쟁이를 구분해 실제 7명의 난쟁이를 찾아내는 문제다. 일반적으로 2중 for문을 순회하면서 모든 경우의 수를 확인해 보는 문제인데, python이 가진 combinations 함수를 사용하면 굳이 일일히 2중 for문을 쓸 필요가 없이 간단하게 해결이 가능했다. 간단한 사용법은 아래와 같다.

from itertools import combinations

candidate = [1,2,3,4,5,6,7,8,9]
combi = combinations(candidate,7)
for i in combi:
    print(sum(i))
    # bla bla

brute force문제를 풀 때 유용하게 사용할 수 있을 것 같다.