오늘 배운 내용
- 코드의 순서 떄문에 발생한 문제 원인 분석과 해결
코드의 순서 떄문에 발생한 문제 원인 분석과 해결
코드 테스트 문제를 풀면서 발생한 문제다. 프로그래머스 - 피로도
문제를 풀떄 처음에는 어떻게 좋은 조건의 던전을 골라야 하는지를 고민했다.
그런데 문제의 제시사항을 보니 던전의 갯수가 8개 밖에 안되어서 모든 경우의수를 고려하는 방법이 떠올랐다.
그렇게 재귀를 사용해 문제를 풀려고 하다보니 던전을 선택해서 입장하고 나면 선택한 던전별로 별도의 남은 던전 리스트가
필요했고 깊은 복사를 이용해서 메서드를 시작할때 queue를 복사하고 복사한 queue로 선택후 남은 던전을 넘겨주는 방벙을 생각해 냈다.
또, 선택별로 영향을 미치지 않도록 재귀 호출을 한후 다시 queue에 넣어서 원본 던전 리스트를 유지해주었다 (순서는 다르겠지만 순서는 상관없었으니)
그렇게 문제를 완벽하게 풀었다고 생각했는데 테스트케이스가 절반정도 날아갔다.
이유를 못찾겠어서 진짜 많은 시간 생각한 끝에 해결하지 못하는 경우의 수를 찾을 수 있었다.
using System;
using System.Collections.Generic;
public class Solution {
int answer = 0;
public int solution(int k, int[,] dungeons)
{
Queue<int[]> queue = new Queue<int[]>();
for(int i =0; i< dungeons.GetLength(0); i++)
{
queue.Enqueue(new int[]{dungeons[i,0], dungeons[i,1]});
}
RecursiveDungeon(0, k, queue);
return answer;
}
public void RecursiveDungeon(int num,int k, Queue<int[]> queue)
{
Queue<int[]> tempQueue = new Queue<int[]>();
// queue를 깊은복사.
foreach (int[] arr in queue)
{
tempQueue.Enqueue(arr);
}
// 길이가 0이라면 끝
if(tempQueue.Count == 0)
{
answer = Math.Max(answer, num);
return;
}
int length = tempQueue.Count;
// queue의 요소 갯수만큼 반복
// 다음 재귀에는 각각의 요소를 선택하고 남은 큐를 복사해서 사용하게됨
for(int i =0; i <length; i++)
{
int[] temp = tempQueue.Dequeue();
if(temp[0] <= k)
{
RecursiveDungeon(num+1, k-temp[1], tempQueue);
tempQueue.Enqueue(temp);
}
}
}
}
내가 찾아낸 경우의수는 만약에 이번선택 이후에 던전리스트의 길이가 0 이상이지만
더이상 입장할 수 있는 던전은 없을때가 문제였다. 보면 Count==0를 체크하기위해서
입장이 불가능한 던전을 날리기 전에 num을 업데이트 하고 있다.
예를 들어서 방문한 던전수 2, 남은 피로도가 10인데 남은 던전 리스트에는 최소 피로도가 전부 10 초과인 상황에서
Count == 0 이 아니기 때문에 answer에 방문 던전수 2는 업데이트 되지않는다.
그런데 방문할수 없는 던전을 Dequeue()하는 부분에서 모든 던전을 날려버리게되고
재귀호출을 하지않아 방문 수 2가 업데이트 되지 않은채로 메서드가 끝나버리게 된다.
중간에 Count를 체크하는 부분은 사실 Count가 0인데 Dequeue()하려는 상황을 막기 위해서 였는데
생각해보니 어차피 처음 Count만큼만 반복할 것이기 떄문에 그런 상황은 발생하지 않았다.
그래서 Count를 체크하는 부분을 아래로 내려서 문제를 해결할 수 있었다.
using System;
using System.Collections.Generic;
public class Solution {
// 길이체크를 앞에서 하면 안되는 이유
// 만약 이번 선택을 하고나면 남은 모든 던전은 갈수 없을때
// 길이체크를 앞에서하게되면 num이 업데이트 되지않아서 num을 업데이트 하지않고 함수가 종료됨
// 원래 처음에 길이체크를 앞에서 한 이유는 인덱스 범위를 벗어날까봐였는데
// 생각해보니 반복문을 통해서 인덱스의 길이를 한번체크하기때문에 그렇게할 필요가없었다.
int answer = 0;
public int solution(int k, int[,] dungeons)
{
Queue<int[]> queue = new Queue<int[]>();
for(int i =0; i< dungeons.GetLength(0); i++)
{
queue.Enqueue(new int[]{dungeons[i,0], dungeons[i,1]});
}
RecursiveDungeon(0, k, queue);
return answer;
}
public void RecursiveDungeon(int num,int k, Queue<int[]> queue)
{
Queue<int[]> tempQueue = new Queue<int[]>();
// queue를 깊은복사.
foreach (int[] arr in queue)
{
tempQueue.Enqueue(arr);
}
int length = tempQueue.Count;
// queue의 요소 갯수만큼 반복
// 다음 재귀에는 각각의 요소를 선택하고 남은 큐를 복사해서 사용하게됨
for(int i =0; i <length; i++)
{
int[] temp = tempQueue.Dequeue();
if(temp[0] <= k)
{
RecursiveDungeon(num+1, k-temp[1], tempQueue);
tempQueue.Enqueue(temp);
}
}
// 길이가 0이라면 끝
if(tempQueue.Count == 0)
{
answer = Math.Max(answer, num);
return;
}
}
}
문제를 해겷하면서 알고는 있었지만 코드의 순서가 약간 변하는것으로 문제를 해결하거나 해결못하는 일이 생길수 있다는것을 체감했고,
코드를 작성할 때 내가 필요한 순서에 맞도록 제대로 구현하는것에 집중을 할 필요성을 느꼈다.
