[프로그래머스] Level 2_피로도(완전탐색)

📌문제 유형

완전탐색

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(57.9)

 - 최소 피로도로 정렬해서 하나 탐색 후, 소모 피로도로 정렬해서 나머지 탐색

 - 최소 피로도 같은 경우, 탐색 기준이 없음

def solution(k, dungeons):
    answer = 0
    
    dungeons.sort(key = lambda x: x[0], reverse = True)
    
    if dungeons[0][0] <= k:
        k -= dungeons[0][1]
        answer += 1
        del dungeons[0]
        
    dungeons.sort(key = lambda x: x[1])
    for i in range(len(dungeons)):
        if dungeons[i][0] <= k:
            k -= dungeons[i][1]
            answer += 1

    return answer

2차 시도(시간초과)

 - range 이용하여 시간복잡도 증가

from itertools import permutations

def solution(k, dungeons):
    max_trip = []
    real_k = k
    all = list(permutations(dungeons,3))
    
    for i in range(len(all)):
        answer = 0
        k = real_k
        for j in range(len(dungeons)):
            if all[i][j][0] <= real_k:
                k -= all[i][j][1]
                answer += 1
        if answer == len(dungeons):
            return len(dungeons)
        max_trip.append(answer)
        
    return max(max_trip)

3차 시도(84.2)

 - (k - 최소피로도) - (k - 소모피로도) 를 이용한 정렬

 -  (k - 최소피로도) - (k - 소모피로도)가 같을 때, 정렬 기준이 없음

def solution(k, dungeons):
    answer = 0
    new_0, new_1, new = 0,0,0
    order = []
    new_order = []
    
    for i in range(len(dungeons)):
        new_0 = abs(k - dungeons[i][0])
        new_1 = abs(k - dungeons[i][1])
        new = abs(new_0 - new_1)
        order.append([i, new])
    order.sort(key = lambda x:x[1], reverse = True)

    for i in range(len(order)):
        if dungeons[order[i][0]][0] <= k:
            k -= dungeons[order[i][0]][1]
            answer += 1
            
    return answer

4차 시도(통과)

- 2차 시도와 유사, temp에 숫자를 담아서 range 구현과 유사하게 제작
(다른 사람 풀이 참조)

from itertools import permutations

def solution(k, dungeons):
    max_num = 0
    temp = [i for i in range(len(dungeons))]
    all = list(permutations(temp,len(dungeons)))
    
    for i in all:
        answer = 0
        change_k = k
        for j in i:
            if dungeons[j][0] <= change_k:
                change_k -= dungeons[j][1]
                answer += 1
            else:
                break
        max_num = max(max_num,answer)
        
    return max_num

 

📌다른사람들의 풀이

1) 한 줄 코드

•  d[ :i] + d[i+1: ] 로 자기자신 제외하고 모든 값 순회

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])

 

2) DFS 사용

• visited를 1로 바꾸기 -> 재귀 실행 -> 0으로 다시 초기화
  • 순서 변경해서 탐색하기 위해 0으로 초기화

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

3) 던전의 효율성 이용

• (최소 + 소모) / (최소)로 효율성 체크, 같은 경우에는 (소모)가 낮은 것으로 정렬

최소피로도가 높으면 우선순위 우선, 소모피로도가 높으면 우선순위 뒤로 감

def solution(k, dungeons):
    answer = 0
    dungeons = sorted(dungeons, key = lambda x : ((x[1]+x[0])/x[0],x[1]))
    for x,y in dungeons:
        print("x :", x, "y : ", y)
        if k >= x:
            k -= y
            answer += 1
    return answer

 

4) permutation 이용

• 2차 시도와 유사
  • range로 접근하면 시간 초과, 리스트 자체를 받아서 쓰면 가능
    -> range를 사용하면 시간복잡도 높아진다.

import itertools

def solution(k, dungeons):
    answer = -1
    visited = 0
    
    for dungeon_permutations in itertools.permutations(dungeons):
        have, count = k, 0
        for need, cost in dungeon_permutations:		# need : 최소, cost  : 소모
            if have >= need and have >= cost:
                have -= cost
                count += 1
        visited = max(visited, count)
        
    answer = visited
    
    return answer

 

📌리뷰

 - permutation 이용 시, list 자체로 순회하기

 - DFS 사용하기