[algorithm] 페어 - 프로그래머스: 피로도

답: 

우옹 내가 이걸 풀다니>.<

from itertools import *

def solution(k, dungeons):
    # 던전을 들어가는 순서를 담은 순열, 각각의 순열에대한 값을 담아줄 dict 생성
    dungeon_datadic = {}
    dungeon_dataset = list(permutations(dungeons, len(dungeons)))
    for number in range(len(dungeon_dataset)):
        dungeon_datadic[number] = 0 

    #데이터 셋은 모든 경우의 수를 포함하고 있으므로, 맨 앞에서부터 시도하여 dic의 각 위치에 시도 횟수 더해주기
    for key, value in dungeon_datadic.items():
        hp = k #very good! 팀원 어시!
        for length in range(len(dungeons)):
            if hp >= dungeon_dataset[key][length][0]:
                dungeon_datadic[key] += 1
                # 입장 후 퇴장할때 hp - 소모 피로도로 유효성 점검
                hp = hp - dungeon_dataset[key][length][1]
            else:
                break
    answer = sorted(dungeon_datadic.items(), key=lambda x: x[1], reverse=True) #내림차순 정렬
    return answer[0][1]

print(solution(80, [[80,20],[50,40],[30,10]])) #3

 

 

하지만 스승호님이 너무 강했따 >> 노션과 다른 사람 풀이보고 공부하기

소수찾기의 원수!

 

 

 

문제 분석 및 해석

 

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

ㅋㅋㅋ갑자기 나타난 어려움.. 이전 문제에서 충분히 고통받았다고 생각했는데 그 위가 있었다^.^

 

'''

k 현재 피로도

던전을 시작하는 ['최소 필요 피로도' // 마치면 소모되는 '소모 피로도']

 

입장시 최소 필요 피로도보다 유저 피로도가 낮으면 입장불가,

입장 후 퇴장할때 k = k - 소모 피로도

 

입장, 피로도 조건 만족하면 최대 던전 수 +

최대 수 반환하기

'''

 

고민 고민...

이차원 배열을 조회하여 소모 피로도가 현재 피로도를 넘지 않는 정도의 값이 최대 던전 수 인데..

소모 피로도 순으로 입장? = 필요 피로도 만족을 못하게 될 수 있음 

필요 피로도 순으로 입장하되 현재 피로도를 만족하지 못하면 최대에서 -1해서 던전 다른 곳?

 

입장 후 퇴장할때 k = k - 소모 피로도로 유효성 점검

 

모든 조건을 검사하고 비교하는 수밖에 없을 것 같다

 

들어가는 순서를 순열로 만들고

성공할시 +1씩 해주기

가장 높은 것을 return

 

 

 

 

* 내가 생각한 풀이

완전 탐색이니 모든 경우의 수를 고려해야할 것이라 생각,

itertools의 순열로 모든 경우의 수를 list에 담고,

해당 경우의 수를 기록해줄 len(list)하여, key는 순서 value=0인 dict 만들기 (엊그제, 어제 팀원분들의 dict활용이 스쳐지나감!)

던전에 들어가서 for문으로 적절한 던전 값을 찾아 굴려주면서 성공한 횟수 dict에 기록

기록한 value들 중 가장 큰 값 뽑아내어 반환

 

 

 

 

 

*찾아본 것 

dict value에서 가장 큰 값을 찾기

 

sorted(dic.items(), key=lambda x: x[1]) #오름차순 정렬

sorted(dic.items(), key=lambda x: x[1], reverse=True) #내림차순 정렬

 

아무래도 dict활용하는 알고리즘을 좀 풀어야겠다..

 

 

 

 

 

 

과정1

 

itertools로 permutations활용, 순열 만들기

각각 순열의 성공값을 담을 dictionary 만들기

key값 = 순열의 index값이 되도록 만들었다.

 

from itertools import *

def solution(k, dungeons):
    # 던전을 들어가는 순서를 담은 순열
    dungeon_datadic = {}

    dungeon_dataset = list(permutations(dungeons, len(dungeons)))
    for number in range(len(dungeon_dataset)):
        dungeon_datadic[number] = 0 
    # print(dungeon_datadic) #{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
    # print(dungeon_dataset[0]) #([80, 20], [50, 40], [30, 10])
    # print(dungeon_dataset[0][0]) # [80, 20]
    # len(dungeon_dataset) = 6  >>경우의 수 갯수!

 

이후 풀이를 위해 각각의 데이터를 출력하여 값을 확인하였다.

 

이 과정이 나에게는 매우 중요했는데,

아직 머리 속으로 완전한 로직이 돌아가지 않는 초보에게 매우매우매우 중요한 작업!!

 

 

 

 

 

과정2

 

데이터 셋은 모든 경우의 수를 포함하고 있으므로, 맨 앞에서부터 시도하여 dic의 각 위치에 시도 횟수 더해주기

참고하기 좋게 print한 것을 붙여두자.

 

# print(dungeon_datadic) #{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
# print(dungeon_dataset[0]) #([80, 20], [50, 40], [30, 10])
# print(dungeon_dataset[0][0]) # [80, 20]

for key, value in dungeon_datadic.items():
    # print(key) # 0 1 2 3 4 5 / value는 0임!
    for length in range(len(dungeons)):
        # print(length)  # 0 1 2
        if k >= dungeon_dataset[key][length][0]:
            dungeon_datadic[key] += 1
            # 입장 후 퇴장할때 k = k - 소모 피로도로 유효성 점검
            k = k - dungeon_dataset[key][length][1]
        else:
            break

 

 

dic의 key값이 순열list index값과 동일하다는 점을 이용해서, 각각의 값을 조회할 수 있도록 했다. = key

 

순열 1개의 길이는 dungeons 요소 길이와 동일하게 3 이므로

for문 안에서 각각의 던전을 조회하기 위해 반복문으로 length를 설정했다.   = length 

 

이후 1개 던전에 담긴 [필요피로도:소모피로도] 는 모든 던전이 동일하니 [0], [1]로 조회하도록 하였고,

필요 피로도 부분에서 조건을 만족하면 dict[key]로 불러온 value값에 성공했다는 의미로 +1 

 

한 던전에 입장 후 퇴장할때 유저의 현재 피로도(k)에서 소모피로도([1])가 - 되도록 했다

 

 

 

 

 

 

여기에서 문제가 생겼는데,

dungeon_datadict를 프린트해보면 {0: 2, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},

맨 첫번째 던전만 들어가고 끝나는 문제가 생겼다.

생각컨데, 유저의 현재피로도 값인 k값이 0번째 순열을 실행한 후 회복되지 않는 문제인 것 같았다.

그래서 나머지 던전을 들어가기 위해 k값을 회복시키고자 고민했는데,

 

 

1) if문안에서 회복시키기 : 모든 던전을 피로도 소모없이 돌아버림!  #  {0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3},

 

 

2) for문안의 for문, 두번째 for문에서 회복시키면 : 결과변화 없음  # {0: 2, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}

 

 

3) 첫번째 for문에서 회복시키기 : 가 맞을 것 같았다!  그런데 변화가 없어서 당황함 #{0: 2, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}

for key, value in dungeon_datadic.items():
    k = k
    for length in range(len(dungeons)):
        if ...

 

 

 

 

결국 페어프로그래밍하던 팀원 분께 SOS를 쳤는데, 참고용으로 잠깐 코드를 보여주셨다!

k를 다른 변수에 저장하는 것!!!!!!이 필요했다.

그렇지 않으면 k가 계속 기본값으로 들어가거나 소모된 상태로 유지되므로.. 위와 같은 값들이 나왔던 거였음.

아래와 같이 수정했다

 

for key, value in dungeon_datadic.items():
    hp = k
    for length in range(len(dungeons)):
        if hp >= dungeon_dataset[key][length][0]:
            dungeon_datadic[key] += 1
            # 입장 후 퇴장할때 k = k - 소모 피로도로 유효성 점검
            hp = hp - dungeon_dataset[key][length][1]
    else: ...

 

 

 

 

 

 

과정3 

dict에서 가장 높은 value값 뽑아내어 반환하기

 

 

찾아 본 자료를 바탕으로 적절하게 코드 변환, 답을 반환하였다.

 

answer = sorted(dungeon_datadic.items(), key=lambda x: x[1], reverse=True) #내림차순 정렬
return answer[0][1]


# 코드 순서는 안맞지만 출력값들!
print(dungeon_datadic) # {0: 2, 1: 3, 2: 1, 3: 2, 4: 1, 5: 2}
print(answer) # [(1, 3), (0, 2), (3, 2), (5, 2), (2, 1), (4, 1)]

 

 

 

 

 

 

---

느낀점: 

 

보기에 복잡해 보이는 문제도 하다보면 풀리니까 포기하지 말고 끝까지 도전하자

는 머리 아파서 산책다녀와야겠음