99클럽 코테 스터디 22일차 TIL: 기본 완전 탐색

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

어쩌다보니 오늘도 프로그래머스 문제이다. 이러면 백준 스트릭 채우려면 1문제를 더 풀어야하는데… 라는 생각이 들기도 하고 여태까지 풀었던 프로그래머스 문제들 중 크게 어려운 문제가 없어서 더 실망하는 듯하다. 특히 이번에도 브루트포스라 난이도가 그리 어렵지 않을 듯하다.

아이디어: 결국은 완전탐색. 8!이면 수가 4만 정도밖에 되지 않음.

말 그대로 전부다 한번씩 선택하여 돌려봐도 시간 초과가 날 일은 없다는 것이다. 그래서 무지성으로 코드를 짜보면 되겠다고 생각했다.

def solution(k, dungeons):
    answer = 0
    
    for dungeon in permutations(dungeons):
        for go in product([0,1],repeat=len(dungeons)):
            hp=k
            m=0
            for idx in range(len(dungeons)):
                if go[idx]==0: continue
                else:
                    if dungeon[idx][0]<=hp:
                        hp-=dungeon[idx][1]
                        m+=1
            answer=max(m,answer)
    return answer

하지만 이렇게 짤 경우 몇몇 케이스가 시간 초과가 난다는 것을 알아냈다. 근데 생각해보면 굳이 [0,1] 배열을 만들지 않아도, 각 순열 별로 앞에서부터 돌려도 되는게 아닌가 하는 생각이 들었다.

from itertools import permutations, product

def solution(k, dungeons):
    answer = 0
    
    for dungeon in permutations(dungeons):
        hp=k
        m=0
        for idx in range(len(dungeons)):
                if dungeon[idx][0]<=hp:
                    hp-=dungeon[idx][1]
                    m+=1
                else: break
        answer=max(m,answer)
    return answer

순열을 썼지만 굳이 그걸 또 들어갈지 말지를 계산하는건 쓸모 없는 연산을 2번 한 것이었다. 이렇게 줄이니 충분히 단순한 코드가 만들어졌다.

오늘의 회고

솔직히 초반에 약간 막막하긴 했지만 파이썬의 itertools를 이용하면 꽤나 문제없이 풀린다는 사실을 기억해냈다. 다른 product 같은 것도 이용해보려 했는데 이 문제에선 그리 필요하지 않았던 듯하다.

약간 완전탐색을 얕보고 틀리긴했지만, 확실히 가장 간단한 방법으로 해결하니 문제없이 풀리긴 했다.