코딩 테스트/Level 2
피로도
컴닥
2021. 10. 30. 22:31
반응형
https://programmers.co.kr/learn/courses/30/lessons/87946
코딩테스트 연습 - 12주차
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던
programmers.co.kr
파이썬 순열과 조합
표준 라이브러리 파이썬에서는 순열과 조합을 사용하고 싶으면, 표준(=기본 내장) 라이브러리를 사용하면 됩니다. 순열은 itertools.permutations, 조합은 itertools.combinations입니다. https://comdoc.tistory...
comdoc.tistory.com
순열을 이용한 전수조사(brute force)...
from itertools import permutations
def solution(k, dungeons):
answer = 0
for permutation in permutations(dungeons):
count, health = 0, k
for required_health, consumed_health in permutation:
if health >= required_health:
health -= consumed_health
count += 1
else:
break
answer = max(answer, count)
return answer테스트 1 〉 통과 (0.03ms, 10.1MB)
테스트 2 〉 통과 (0.03ms, 10.2MB)
테스트 3 〉 통과 (0.05ms, 10.3MB)
테스트 4 〉 통과 (0.08ms, 10.1MB)
테스트 5 〉 통과 (0.42ms, 10.3MB)
테스트 6 〉 통과 (3.54ms, 10.3MB)
테스트 7 〉 통과 (39.58ms, 10.2MB)
테스트 8 〉 통과 (42.90ms, 10.2MB)
테스트 9 〉 통과 (0.05ms, 10.2MB)
테스트 10 〉 통과 (2.65ms, 10.1MB)
테스트 11 〉 통과 (0.02ms, 10.2MB)
테스트 12 〉 통과 (24.17ms, 10.1MB)
테스트 13 〉 통과 (13.83ms, 10.3MB)
테스트 14 〉 통과 (13.10ms, 10.1MB)
테스트 15 〉 통과 (12.60ms, 10.2MB)
테스트 16 〉 통과 (1.62ms, 10.3MB)
테스트 17 〉 통과 (13.25ms, 10.2MB)
테스트 18 〉 통과 (0.01ms, 10.3MB)
테스트 19 〉 통과 (0.05ms, 10.2MB)
직접 순열을 만들면
만드는 과정에서
답을 찾을 수 있기 때문에
효율적입니다.
def solution(k, dungeons):
def dfs(count, health, visited):
nonlocal answer
for i, (need_tired, use_tired) in enumerate(dungeons):
if not visited[i] and need_tired <= health:
visited[i] = True
dfs(count + 1, health - use_tired, visited)
visited[i] = False
answer = max(answer, count)
answer = 0
dfs(0, k, [False for _ in range(len(dungeons))])
return answer테스트 1 〉 통과 (0.03ms, 10.1MB)
테스트 2 〉 통과 (0.05ms, 10.1MB)
테스트 3 〉 통과 (0.02ms, 10.2MB)
테스트 4 〉 통과 (0.22ms, 10.1MB)
테스트 5 〉 통과 (0.93ms, 10.2MB)
테스트 6 〉 통과 (2.78ms, 10.1MB)
테스트 7 〉 통과 (15.61ms, 10.2MB)
테스트 8 〉 통과 (41.47ms, 10.3MB)
테스트 9 〉 통과 (0.03ms, 10.1MB)
테스트 10 〉 통과 (0.88ms, 10.2MB)
테스트 11 〉 통과 (0.01ms, 10.1MB)
테스트 12 〉 통과 (1.99ms, 10.2MB)
테스트 13 〉 통과 (0.25ms, 10.1MB)
테스트 14 〉 통과 (0.09ms, 10.3MB)
테스트 15 〉 통과 (0.07ms, 10.3MB)
테스트 16 〉 통과 (0.04ms, 10.1MB)
테스트 17 〉 통과 (0.17ms, 10.3MB)
테스트 18 〉 통과 (0.02ms, 10.2MB)
테스트 19 〉 통과 (0.07ms, 10MB)
자바
class Solution {
int[][] dungeons;
int answer = 0;
void dfs(int tired, boolean[] check, int cnt) {
for (int i = 0; i < dungeons.length; i++)
if (!check[i] && dungeons[i][0] <= tired) {
check[i] = true;
dfs(tired - dungeons[i][1], check, cnt + 1);
check[i] = false;
}
answer = Math.max(answer, cnt);
}
public int solution(int k, int[][] dungeons) {
this.dungeons = dungeons;
dfs(k, new boolean[dungeons.length], 0);
return answer;
}
}테스트 1 〉 통과 (0.14ms, 78.9MB)
테스트 2 〉 통과 (0.03ms, 74.2MB)
테스트 3 〉 통과 (0.03ms, 76.6MB)
테스트 4 〉 통과 (0.15ms, 78.7MB)
테스트 5 〉 통과 (0.49ms, 82.1MB)
테스트 6 〉 통과 (0.54ms, 74.9MB)
테스트 7 〉 통과 (1.30ms, 77.2MB)
테스트 8 〉 통과 (2.56ms, 77.4MB)
테스트 9 〉 통과 (0.05ms, 73.3MB)
테스트 10 〉 통과 (0.43ms, 74.3MB)
테스트 11 〉 통과 (0.09ms, 77.6MB)
테스트 12 〉 통과 (0.49ms, 82.7MB)
테스트 13 〉 통과 (0.12ms, 79.8MB)
테스트 14 〉 통과 (0.07ms, 77MB)
테스트 15 〉 통과 (0.05ms, 78.1MB)
테스트 16 〉 통과 (0.06ms, 79.4MB)
테스트 17 〉 통과 (0.06ms, 77.8MB)
테스트 18 〉 통과 (0.11ms, 77.1MB)
테스트 19 〉 통과 (0.06ms, 68MB)반응형