99클럽 코테 스터디 1일차 TIL - permutations

Python에는 itertools 라이브러리로 순열과 조합을 쉽게 구현할 수 있다.

순열, permutations

순열은 n개의 원소를 순서를 정하여 r개의 배열로 나타내는 것이다.

순열은 순서가 있기 때문에 원소의 종류가 같아도 순서가 다르면 다른 배열이 된다.

from itertools import permutations

a = [1, 2, 3]
permute = permutations(a, 2)

print(list(permute)
# [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

오늘의 문제: 프로그래머스 - 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

- 가능한 던전의 순서를 permutations 함수로 정리한다.

- 피로도가 0이 되기 전까지 탐험할 수 있는 던전의 수를 센다.

- 최대 던전 수를 구한다.

풀이

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    N = len(dungeons)
    
    for permutation in permutations(dungeons, N):
        cnt, kk = 0, k
        for dungeon in permutation:
            if dungeon[0] <= kk:
                kk -= dungeon[1]
                cnt += 1
            else:
                break
                
        answer = max(cnt, answer)
    
    return answer

오늘의 회고

- 순열과 조합 문제를 itertools를 사용해 풀고 있지만, for문 또는 재귀함수를 이용해 푸는 방법도 익혀야 할 것 같다.

- 아직까지 시간복잡도를 구하기 익숙치 않다. 많은 유형의 문제를 풀어보며 복잡도를 익히자