[4코1파] #19. 피로도

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (19일차)
[4코1파] 2023.01.13~ (10일차)

Today :

2023.01.22 [19일차]

프로그래머스 LV2.
피로도
https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 요약

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한 사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

입출력 예 설명
현재 피로도는 80입니다.
만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
※ 공지 - 2022년 2월 25일 테스트케이스가 추가되었습니다.

문제 풀이 방법

최소 피로도의 경우의 수에 따라서 cnt를 세야 해서
이번에는 순열을 이용해서 문제를 풀어야 했음
피로도의 순열을 구한후에 주어진 배열을 싹 돌면서 체크하는 문제
처음에는 배열을 돌기 전에 cnt가 주어진 던전의 길이 자체를 넘기면 바로 리턴값을 내보내는 루트로 짜니까 코드도 더러워지고 답도 안맞았음..

처음 짰던 코드

import itertools
import copy

def solution(k, dungeons):
    need = {idx:dungeons[idx][0] for idx in range(len(dungeons))}
    lost = {idx:dungeons[idx][1] for idx in range(len(dungeons))}
    order = [i for i in range(len(dungeons))]
    answer = 0

    print(f"lost -> {lost}")
    print(f"need -> {need}")
    print(f"order ->{order}")

    pers = itertools.permutations(order, len(dungeons))

    for p in pers:
        print(f"p -> {p}")
        tmp_k = copy.deepcopy(k)
        for o in order:
            print(p[o])
            if (tmp_k>= need[p[0]]) & (tmp_k-lost[p[0]]>=0):
                answer +=1 
            if answer == len(dungeons):
                return len(dungeons)
            
    return answer

그래서 그냥 정석적으로 순열을 구하고,
순열 내의 던전을 돌면서 조건에 맞는거만 카운트 하는 식으로 변경함
시간복잡도에서 박살날 줄 알았는데 아니였음

내 코드

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    pers = permutations(dungeons, len(dungeons))
    for per in pers:
        cnt = 0
        tmp_k = k
        for p in per:
            if tmp_k>=p[0]:
                tmp_k-=p[1]
                cnt +=1
            if cnt > answer :
                answer = cnt
            
    return answer

다른 사람 풀이

이걸 한줄 코딩 하는 새럼이 있네..

부럽네... 재수없고...
좋은말 할때 내 코드로 만들자

2
solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])

여담

피로해서 홀린 듯 누른 피로도 문제
풀었는데도 여전히 피곤하다