오늘은 3 문제를 업로드할 예정이다. 하루에 3문제를 푼 것은 아니고 오늘까지 사실 4문제를 풀었지만 1문제는 아직 제대로 이해하지못해 업로드가 불가능하다고 판단했다.
어제 오늘 2일 동안 골머리를 앓았던 문제가 있다.
프로그래머스 - level2: 줄서는 방법
이 문제는 DFS로 풀자니 런타임 오류가 발생했고 문제의 규칙성을 이해하는데 한참 헤맸다. 어제 오늘 고생한 문제 + 오늘 푼 3문제 중 2 문제를 뽑아 3문제를 업로드 할 계획이다. 문제로 바로 넘어가자!
줄서는방법 ❓
문제만 보면 굉장히 간단하다.
자, 그냥 dfs를 활용해서 줄 서는 방법을 모두 두한 후 k번째 index를 return 해주면 될 거 같지 않나? 그렇게 풀어본 코드는 다음과 같다.
function solution(n,k){
const answer=[]
const arr = Array.from({length:n},(v,i)=>i+1)
//arr을 형성
const visited = Array.from({length:n},()=>false)
//방문 기록을 위한 arr 생성
const dfs=(sum,count)=>{
if(count===n){
answer.push(sum)
return;
}
for(let i = 0 ; i < n; i++){
if(!visited[i]){
visited[i]=true
dfs(sum+arr[i],count+1)
visited[i]=false
}
}
}
dfs(``,0)
return answer[k-1].split(``)
}이런식으로 dfs를 활용해서 모든 경우를 만들어 줄 수도 있지만 k가 n!까지의 범위이다. 그렇다면 n이 20일 경우 그 값이 너무 커진다.
그럼 그냥 k의 값을 가지고 바로 어떤 배열이 나올지 계산해야한다. 그게 가능한 로직이있는지 몰랐다. 하지만 천천히 들여다 보면 규칙성을 발견할 수 있다.
완전탐색이 아닌 규칙성 발견 ❗️
자 n=3 k=4 일 경우를 생각해보자
[1,2,3]을 가지고 만들 수 있는 순서의 종류는
123 132 213 231 312 321
이렇게 6가지이다. 일단 줄세우는 경우의 수는 N! 이다. 그러면 6가지임을 알 수 있고 배열의 길이 즉, 몇명을 대상으로 줄을 세우는지에 대한 수를 전체 경우의 수에서 나누어주면 Index를 통해 처음으로 오는 숫자를 예측할 수 있다.
n! => 6 사람 수=> 3 그러므로 2 2 2 가 되는데 이는 k가 2까지는 index 0 인 1이 오고 4까지는 index1 인 2가 오고 k가 6까지는 index 2인 3이온다.
이를 이용하고 나머지를 통해 k와 n을 변경해주며 반복문을 돌리면 원하는 순서를 구할 수 있다.
자 코드로 한번 살펴보자
코드로 살펴보기 ❗️
function solution(n,k){
const answer =[]
const arr = Array.from({length:n},(v,i)=>i+1)
// 기준이 되는 arr을 생성한다.
let caseOfAll = arr.reduce((acc,cur)=>acc*cur,1)
// 모든 경우의 수를 먼저 구했다.
while(n>0){
const range = caseOfAll/n
// 범위를 구한것이다. 어떤 범위? Index가 나누어지는 범위
let index = Math.floor(((k-1)/range))
// 왜 K-1?? => 자, 만약 range가 6인데 그럼 6번째 까지는 0의 인덱스가 나온다는 건데 k/range해버리면 1이 나와버린다. 그게 아니라 index로 접근해야하니까 k-1을 해준 후 Math.floor를 한다.
// 근데 여기서 index가 -1이 되는 경우가 발생할 수 있다.
// k가 딱 맞아 떨어진다는 건 ??? 가장 맨 마지막이라는거
// 그렇기 때문에 조건문을 걸어 k를 재할당 해주어야한다.
if(index===-1){
index=n-1
}
answer.push(arr[index])
// 원하는 index를 push해주고
arr.splice(index,1)
// arr에서는 빼주어야 계속해서 원하는 index를 받아 갈 수 있음
k = k%range
// 나머지는?? 몇 번째인지가 되면서 다시 k를 재할당할 수 있음
// 예를 들어 k=7이거 범위가 6이라면 ?? 7은 두 번째 인덱스에서 가장 첫 번째 인 것이다.
caseOfAll=caseOfAll/n
// 총 경우의수도 변화가 생기고
n=n-1
//n은 하나 빠져나갔으니 1이 감소되어야한다.
}
return answer
}자세한 사항은 주석에 처리를 해주었다.
다음과 같이 Input이 너무나 크다면 규칙성을 발견해주어야한다.
배달 ❓
위 문제는 그렇게 이해하기 어렵지 않았다.
마을이 N개 있고 체력이 0이될때까지 몇개의 마을을 갈 수 있는지를 살펴보면된다.
즉 재귀적으로 풀 수 있다. BFS로 문제를 해결하였다. K의 체력과 같거나 작을 때 까지는 계속해서 다음 목적지를 찾아갔고 그러다 체력을 다쓰면 return을 통해 빠져나오면 된다. 그럼 재귀함수의 인자에는 지금의 위치와 체력이 필요하다.
먼저 지금 내 위치는 1이 된다. 왜냐면 항상 1번 마을에서 출발한다고 문제에 나와있기 때문이다. 체력은 0에서 출발하면된다.
코드로 살펴보기 ❗️
function solution(N,road,K){
const visited = Array.from({length:N},()=>false)
const answer=[]
const bfs=(currentCity,hp)=>{
if(hp>K){
return ;
}
if(!answer.includes(currentCity)){
answer.push(currentCity)
}
for(let i = 0 ; i < road.length; i++){
if(!visited[i] && currentCity===road[i][0]){
visited[i]=true
//방문처리를통해 다시 돌아와서 다른 경우도 살펴볼 수 있다.
bfs(road[i][1],hp+1)
visited[i]=false
}
}
}
bfs(1,0)
return answer.length
}다음과 같이 방문한 지역을 모두 체크할수있다!!!
근데 여기서 놓친점이 있었다. 바로 도시를 연결한느 road의 0,1번인덱스는 방향성이 없다는 점 ! 그냥 길일 뿐이다. 그렇기 때문에 순서를 고려하지 않아야한다.
function solution(N, road, K) {
const visited = Array.from({length: N},()=>false)
//1번은 먼저 방문하고 시작하니까
const answer =[]
const bfs=(currentCity,time)=>{
if(time>K){
return;
//배달 시간 오바하면 종료
}
if(!answer.includes(currentCity)){
answer.push(currentCity)
}
for(let i = 0 ; i < road.length; i++){
//방문안했고 road[i]가 현재 마을과 같다면 Go
if(!visited[i]&&road[i][0]){
if(road[i][0]===currentCity){
visited[i]=true
bfs(road[i][1],time+road[i][2])
visited[i]=false
}
else if(road[i][1]===currentCity){
visited[i]=true
bfs(road[i][0],time+road[i][2])
visited[i]=false
}
}
}
}
bfs(1,0)
return answer.length
}이렇게 수정할 수 있다. 결과는 ???
32번 테스트 케이스를 실패해 96.9점이다.
질문하기 카테고리를 통해 알아낸 사실은 bfs 알고리즘으로 통과할 수 없고 다른 플로이즘 알고리즘, 다익스트라 알고리즘을 사용해야 풀 수 있다고한다.
지금은 dfs/bfs를 배우기도 벅차니 일단 이 알고리즘을 체득하면 그리고 그 다음 심화된 알고리즘을 학습해보자 !
여행경로 ❓
이 문제는 1달전 쯤 시도를 했었는데 75점이 나왔었다..!
혹시나 하고 지금 다시 풀어봤더니..! 바로 PASS!!
기분이 참 좋았다. 어제는 1문제로 하루종일 골머리를 앓았는데 오늘은 또 이런 성취감이! ㅎㅎ
위 배달 문제와 매우 흡사하다.
일단 현재 위치한 공항에서 방문하지 않은 다음 공항으로 가고 만약 모든 공항을 방문했다면 ?? 그때의 결과를 answer에 push한 후 알파벳순서로 정렬 후 0번인덱스를 return하면 되는 문제이다.
코드로 살펴보기 ❗️
function solution(tickets){
const answer=[]
//주어진 항공권을 모두 사용해야하니까
const visited = Array.from({length:tickets.length},()=>false)
const dfs=(currentAirPort,sum)=>{
if(!visited.includes(false)){
answer.push(sum+currentAirPort)
return;
}
for(let i = 0; i<visited.length; i++){
if(!visited[i]&¤tAirPort===tickets[i][0]){
visited[i]=true
dfs(tickets[i][1],sum+`${tickets[i][0]},`)
visited[i]=false
//이렇게 ,를 넣어주는 이유는 나중에 split(`,`)을 통해 배열로 바꿔주기 위해서 !
}
}
}
dfs("ICN",``)
answer=answer.map((item)=>item.split(`,`).join(`,`)).sort((a,b)=>a>b?1 :-1).map((item)=>item.split(`,`))
return answer[0]
}
이렇게 풀어보니 굉장히 간략하게 잘 풀린거 같다. 필자가 풀었던 문제 중 가장 뿌듯하다..ㅎ
그럼 이전의 코드는 왜 틀렸던 걸까?
과거의 코드 ❓
function solution(tickets) {
let answer = [];
const ICNIndexArr = tickets
.map((item, index) => (item[0] === "ICN" ? index : null))
.filter((item) => item !== null);
//ICN이있는인덱스를찾음
let visited = Array.from({ length: tickets.length }, () => false);
// 방문확인을위해 배열생성
let target;
const dfs = (firstPort, sum, count) => {
if (count === 0) {
target = firstPort;
}
if (count === tickets.length - 1 && !answer.includes(sum)) {
sum = "ICN" + ` ` + firstPort + ` ` + sum.slice(0, -1);
answer.push(sum);
return;
}
for (let i = 0; i < tickets.length; i++) {
if (visited[i] === false && target === tickets[i][0]) {
visited[i] = true;
target = tickets[i][1];
sum = sum + target + ` `;
count = count + 1;
console.log(sum);
dfs(firstPort, sum, count);
target = tickets[i][0];
}
}
};
for (let i = 0; i < ICNIndexArr.length; i++) {
visited[ICNIndexArr[i]] = true;
dfs(tickets[ICNIndexArr[i]][1], ``, 0);
visited = Array.from({ length: tickets.length }, () => false);
}
answer = answer
.sort((a, b) => (a > b ? 1 : -1))
.map((item) => item.split(` `));
return answer[0];
}
solution(tickets);
흠... 다시보니 불필요한 부분 재귀함수에 대한 이해가 부족해보이는 부분이 상당히 많다..
방문 후 처리도 부족하고 굳이 dfs를 바깥에서 또 반복문으로 실행해준 과정 등
그래도 이 코드를 작성하면서 쏟은 시간 덕분에 또 발전할 수 있지 않을까?
계속해서 전보다 나은 코드를 작성해가는 개발자가 되고싶다..!
오늘의 코딩테스트 정리는 이만하고 필자는 7일 전에 풀어봤던 문제를 다시 접근하러 가보아야겠다. 오늘도 화이팅이다 !
