문제
https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🐍파이썬
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
let, const | PoiemaWeb
ES5까지 변수를 선언할 수 있는 유일한 방법은 var 키워드를 사용하는 것이었다. var 키워드로 선언된 변수는 아래와 같은 특징이 있다. 이는 다른 언어와는 다른 특징으로 주의를 기울이지 않으면
poiemaweb.com
자바스크립트 배열 선언
https://miiingo.tistory.com/272
[Node.js] Javascript: 지정한 길이에 맞게 배열을 선언하고 값을 초기화하는 방법들
배열 선언 및 초기화 방법 길이가 N인 배열 arr을 선언하면서 동시에 값을 초기화하고 싶은 경우 CASE 1: for문 이용 const N = 5; // 길이 N을 5라고 가정 let arr = []; for(let i=0; i
miiingo.tistory.com
DFS
https://han-py.tistory.com/242
[코딩테스트] 쉽게 이해하고 바로 쓰는 DFS (깊이 우선 탐색)
DFS (깊이 우선 탐색) DFS 깊이 우선 탐색은 코딩테스트에서 기본적으로 알아야한다. DFS란 말 그대로 깊이를 우선적으로 탐색하는 방법이다. 좀 더 쉽게 말하면, 갈림길이 있다면 한방향으로 끝까
han-py.tistory.com
'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 |