반응형
문제
https://school.programmers.co.kr/learn/courses/30/lessons/87946
🐍파이썬
from itertools import permutations
def solution(k, dungeons):
result = []
#던전을 방문하는 순서의 경우의 수를 나열
for dg in permutations(dungeons, len(dungeons)):
nk = k #매번 k로 피로도 리셋
answer = 0 #방문한 던전 수 매번 리셋
for d in dg: #각 경우의 수마다 방문할 수 있는 던전 수 확인
if nk >= d[0]: #남은 피로도가 던전의 필요피로도보다 같거나 큰 경우 던전 방문
nk -= d[1] #남은 피로도-소모 피로도
answer += 1 #방문한 던전 수 + 1
result.append(answer)
return max(result) #방문 가능한 최대 던전의 수
❓ 순열
itertools.permutations(iterable, r=None)
- itertools 모듈
- 서로 다른 n개 원소 중 r개를 순서를 고려해 나열하는 경우의 수
- 위 코드의 경우 순열은 아래와 같다.
...
def solution(k, dungeons):
result = []
for dg in permutations(dungeons, len(dungeons)):
print(dg)
# dungeons = [[80,20],[50,40],[30,10]]일때
# 순열의 결과
# ([80, 20], [50, 40], [30, 10])
# ([80, 20], [30, 10], [50, 40])
# ([50, 40], [80, 20], [30, 10])
# ([50, 40], [30, 10], [80, 20])
# ([30, 10], [80, 20], [50, 40])
# ([30, 10], [50, 40], [80, 20])
nk = k
...
다른 풀이 방법
answer = 0
N = 0
visited = []
def dfs(k, cnt, dungeons):
global answer
if cnt > answer: #방문가능한 던전의 갯수(cnt)가 answer보다 더 크다면 리턴할 최대 던전의 갯수를 cnt개로 설정
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) #dfs(현재피로도 업데이트, 방문횟수 체크, 던전배열)
visited[j] = 0 #dfs의 리프노드까지 모두 탐색 후 이전 노드로 돌아왔을 경우, 해당 노드 visited값을 0으로 복구
def solution(k, dungeons):
global N, visited
N = len(dungeons)
visited = [0] * N
dfs(k, 0, dungeons) #방문한 던전갯수 0개
return answer
DFS를 이용한 풀이
🐥자바스크립트
let answer = 0
let cnt = 0
let visited;
function DFS(k, cnt, dungeons){
// 방문가능한 던전의 갯수(cnt)가 answer보다 더 크다면 리턴할 최대 던전의 갯수를 cnt개로 설정
if(cnt > answer){
answer = cnt;
}
for(let i = 0; i < dungeons.length; i++){
// 현재 피로도로 방문할 수 있는 던전이면서 방문하지 않은 던전인 경우
if(k >= dungeons[i][0] && visited[i] == 0){
visited[i] = 1; // 방문처리
DFS(k - dungeons[i][1], cnt+1, dungeons); // DFS(현재피로도 업데이트, 방문횟수 체크, 던전배열)
visited[i] = 0; // DFS의 리프노드까지 모두 탐색 후 이전 노드로 돌아왔을 경우, 해당 노드 visited값을 0으로 복구
}
}
}
function solution(k, dungeons) {
(visited = []).length = dungeons.length;
visited.fill(0); //배열 선언. new Array(N).fill(0)보다 속도가 빠르다고 함
DFS(k, 0, dungeons); //방문한 던전갯수 0개
return answer;
}
위 파이썬 DFS와 동일한 로직으로 풀었다.
참고
자바스크립트 블록 스코프
https://poiemaweb.com/es6-block-scope
자바스크립트 배열 선언
https://miiingo.tistory.com/272
DFS
https://han-py.tistory.com/242
반응형
'Problem Solving > 프로그래머스' 카테고리의 다른 글
[프로그래머스 | 파이썬 / 자바스크립트] 이진수 더하기(코딩테스트 입문/ level 0) (0) | 2023.02.28 |
---|---|
[프로그래머스 | 파이썬 / 자바스크립트] 유한소수 판별하기(코딩테스트 입문/ level 0) (0) | 2023.02.25 |
[프로그래머스 | 파이썬 / 자바스크립트] 대문자와 소문자(코딩테스트 입문/ level 0) (0) | 2023.02.25 |
[프로그래머스 | 파이썬 / 자바스크립트] 다항식 더하기(코딩테스트 입문/ level 0) (0) | 2023.02.24 |
[프로그래머스 | 파이썬 / 자바스크립트] 배열 회전시키기(코딩테스트 입문/ level 0) (0) | 2023.02.24 |
[프로그래머스 | 파이썬 / 자바스크립트] 소인수분해(코딩테스트 입문/ level 0) (0) | 2023.02.24 |