프로그래머스 level2 - (16)

박상하·2023년 5월 1일

목록 보기

16/37

Hi 오랜만 🖖

오랜만에 코딩테스트 문제를 업로딩한다. 짝발란스 웹페이지를 만드는동안 코딩테스트를 아예 하지 않았던 것은 아니다. 시간이 날 때마다 풀어왔었다!!! 하지만 늘 풀면서 블로그로 정리를 하지 못했었고 사실 dfs , bfs를 제외하고 이전에 풀었던 문제들만 풀어보니 블로그를 따로 작성할 동기를 얻지 못하였다. 하지만 최근 코딩 테스트 문제를 풀어나가면서 나의 취약점을 발견하게됐다..!
늘 알고있었지만 미뤄왔던 DFS,BFS를 이번 5월동안 집중공략 해볼생각이다!

프로그래머스 여름방학 인턴프로그램, 또 기업 코딩테스트를 거쳐보면서 코딩테스트에서 약한 모습이 분명 보였다..! 하지만 개발자의 마인드는 무엇인가
꺾여도 그냥 하는 마음!! 그렇게 오늘부터 다시 시작해보겠다. 몇번 꺾일지 모르겠지만 포기하는 일은 없을것이다!🔥 🔥 🔥

피로도

결국 위 문제는 완전탐색 문제로 DFS로 접근하면 된다.

초기에 DFS로 접근을 생각했고 또 queue를 이용하여 visited=[]의 arr을 만들어 방문한 던전과 방문하지 않은 던전을 구분지으려했다. 그렇다면 방문하지 않은 던전이라면 방문해서 피로도를 비교하고 던전에 필요한 피도로가 내가 가진 피로도보다 높으면 그 던전에 들어가서 피로도를 소비하면 된다.

던전을 순회한다.

내 피로도와 던전 필요 피로도를 비교한다.

만약 내 피로도가 더 높고 방문하지 않은 던전이라면 내 피로도 - 던전필요피로도

대략적인 로직은 위 순서와 같이 잡혔다. 그렇다면 어떻게 구현을 할 거인가?

처음엔 fillter함수를 사용해서 visited arr을 변경해가며 구현해보려 하였다.
흠 그렇지만 쉽지 않았다. 답안을 보니 그렇게 구현하신 분도 있었다.

function solution(k, dungeons) {
    const filtered = dungeons.slice().filter(v => v[0] <= k);

    let answer = 0;
    for (let i = 0; i < filtered.length; i++) {
        const subAnswer = solution(k - filtered[i][1],filtered.filter((_, j) => i !== j));
        if (subAnswer + 1 > answer) answer = subAnswer + 1;
    }
    return answer;
}

흠.. 그런데 위 코드를 생각도 못했을 뿐더러 필자는 dfs를 이용해서 해당 문제를 해결하고싶었다.

30분을 고민해도 잘 해결이 되지않아. 다른 분의 코드를 살펴보았다. 참고로 앞으로 코딩테스트 공부법은 변경할 것이다. 왜냐하면 한 문제를 3~4시간 잡고있다보면 체력도 빠지고 의지도 꺾이고 또한 다른 분의 코드를 더더욱 보기 싫어지는 마음이 커기지 때문이다. 다른 분의 코드를 보아야 내 실력향상이 도움되기 때문에 30분봐도 잘 모르겠다면 과감하게 다른 분의 코드를 보고 배울 것이다

필자가 본 코드는 다음과 같다.

function solution(k, dungeons) {
  let answer = 0;
  // 방문했는지 확인하기 위한 배열
  const visited = Array.from({ length: dungeons.length }, () => false);

  // 완전탐색을 위한 DFS(남은 피로도, 진행단계)
  function DFS(hp, L) {

    // 던전의 수 만큼 반복한다.
    for (let i = 0; i < dungeons.length; i++) {

      // 방문하지 않았고 현재 남은 피로도가 최소 필요도 보다 크거나 같으면 실행
      if (!visited[i] && dungeons[i][0] <= hp) {

        // 현재 들어온 던전을 방문 처리
        visited[i] = true;

        // DFS(현재 피로도 - 방문 던전, 진행단계 + 1)
        DFS(hp - dungeons[i][1], L + 1);

        // DFS 종료 후 방문을 끝내준다.
        visited[i] = false;
      }
    }

    // 가장 깊이 들어간 진행단계를 answer에 넣어준다.
    answer = Math.max(answer, L);
  }

  DFS(k, 0);

  return answer;
}

그렇다.. 내가 만들고 싶었던 코드는 바로 이 느낌이다!

그런데 다른점이 있다면 visited에서 방문한 index를 직접관리한다기보단 boolean을 이용해 재귀함수의 속성을 통해 해당 Index의 방문 상황을 실시간으로 저장한다.

이게 무슨 말일까?

재귀함수는 그 시점을 기억한다 ❓

이번 문제를 풀면서 느낀 점은 재귀함수는 그 시점을 기억하고 탈출된다면 다시 어떤 조건을 리셋해주는 것이 중요하다는 것이다.

중요한건

재귀함수는 그 시점을 기억한다.

만약 다음과 같은 코드가 있다면

function solution(){
 const check = [1,2,3,4,5,6]
 
 const dfs=(index,sum)=>{
 if(index>check.length){
  return 
 }
 //이 때 sum을 console에 찍어보면 
   //처음엔 0
   //두 번째 재귀에선 1 
   //세 번째 재귀에선 2 등으로 계속 증가할 것이고 마지막 재귀함수가 종료되고 
 //차츰 하나씩 겉에서 속으로? 함수의 실행이 종료된다면 돌아올 때마다 그 점을 기억한다
   dfs(index+1,sum+check[index])
   
   console.log(sum)
   //그렇기 때문에 여기서 sum은 21,15,10,6,3,1,0 이찍힌다.
 }
 
 dfs(0,0)
}
solution()

다음과 같이 그 시점을 기억하는 것이 재귀함수이다.

그 점을 이용하면 for문 속에 재귀함수도 쉽진 않지만 이해할 수 있다.

다시 아까 그 코드를 살펴보자.

```js
function solution(k, dungeons) {
  let answer = 0;
  // 방문했는지 확인하기 위한 배열
  const visited = Array.from({ length: dungeons.length }, () => false);

  // 완전탐색을 위한 DFS(남은 피로도, 진행단계)
  function DFS(hp, L) {

    // 던전의 수 만큼 반복한다.
    for (let i = 0; i < dungeons.length; i++) {

      // 방문하지 않았고 현재 남은 피로도가 최소 필요도 보다 크거나 같으면 실행
      if (!visited[i] && dungeons[i][0] <= hp) {

        // 현재 들어온 던전을 방문 처리
        visited[i] = true;

        // DFS(현재 피로도 - 방문 던전, 진행단계 + 1)
        DFS(hp - dungeons[i][1], L + 1);

        // DFS 종료 후 방문을 끝내준다.
        visited[i] = false;
      }
    }

    // 가장 깊이 들어간 진행단계를 answer에 넣어준다.
    answer = Math.max(answer, L);
  }

  DFS(k, 0);

  return answer;
}

for문이 i부터 출발하는 건 무엇때문일까 바로 i가 0일때의 모든 경우를 살펴보겠다는 점이다. 왜냐하면 dfs로 인해 for문 속의 for문으로 들어갈 것이기 때문이다.

만약 index가 0 인 던전이 내가 가진 hp보다 낮은 피로도를 요구한다면
그 속으로 들어간다.( 그럼 어떻게 되겠는가? 또 dfs안의 for문으로 들어가 visited가 false인 index를 만나게되면 방문한 던전의 수가 하나 올라가고 계속 for문으로 들어가겠지? )

그렇게 for문에서 나온다면 해당 던전도 나온 것과 같음으로 visited[i]=false 처리를 해주어야한다.

사실 이게 말로 설명하기가 참어렵다는 걸 .. 어쩌면 아직 필자의 머리속에 완벽하게 들어오지 않아 그럴 수 있다. 다시 한번 코드를 보지 않고 내가 이해한 방식으로 이 블로그에 코드를 바로 쳐보도록하겠다!!

function solution(k, dungeons) {
  //방문한 던전의 개수를 저장할 수 있는 arr
  const answer=[]
  //방문했는지를 저장할 수 있는 arr이 필요
  const visited = Array.from({length:dungeons.length},()=>false)
  //여기서 [false,false,false]의 배열을 만들어준다.
  
  //dfs를 써야지
  const dfs=(hp,count)=>{
    for(let i =0 ; i <dungeons.length; i++;){
      // hp조건과 방문조건
   if(!visited[i]&&hp>=dungeons[i][0]){
    visited[i]=true
     dfs(hp-dungeons[i][1],count+1);
     // 던전에서 나오면 false
    visited[i]=false
      
   }   
    }
   
    answer.push(count)
  }
  
  dfs(k,0)
  
 return Math.max(...answer)
}

위 코드를 지금 한 70% 는 이해하고 있는 거 같다. 정답!

이 기세를 몰아 다음 dfs/bfs문제를 시도해보자

줄서는방법

문제는 다음과 같다.
위 문제를 dfs로 접근을 했을 때 위 피로도 문제랑 비슷하다고 생각했다.
해당 위치 visited arr에 for문의 i 변수를 넣으면서 아직 들어가지 않은 i를 전부 알아보는 방법이다. 근데 사실 이 방법은 완전탐색으로 좋아 보이지는 않았다. 하지만 위 내가 했던 방식을 복습하고 또, dfs에 대해 학습할 겸 dfs로 접근을 해보았다.

그럼 먼저 문제를 분석해보면 n의 숫자를 가지고 길이가 n인 배열을 만들 때, 들어갈 수 있는 모든 배열의 경우를 구하면 된다.(겹치지않게) 그런 후 모든 배열의 경우를 사전순으로 나열할 수 있으면 된다.

visited 배열에 방문하지 않은 i를 넣는다. 이때, 숫자는 앞에서부터 사전순으로 넣을 수 있어야 한다.

visited 배열의 길이가 n이 될때를 check한다.

n이 됐던 횟수가 k와 같아질때 그때의 visited를 구하면된다.

코드는 다음과 같다.

let n = 3;
let k = 5;

function solution(n, k) {
  const visited = [];
  let count = 0;
  // 배열이 꽉찼을 때를 셀 수 있는 count
  let answer;
  // 정답을 return할 answer 
  const dfs = () => {
    
 
    //visited의 길이가 n이면 count를 1추가한다.
    if (visited.length === n) {
      count = count + 1;
      //count가  k랑 같아지면 answer은 그때의 visited가 된다.
      if (count === k) {
        answer = [...visited];
      }
    }

    for (let i = 1; i <= n; i++) {
      if (!visited.includes(i)) {
        visited.push(i);
// 없으면 visited.push
        
        dfs();
        // 그 후 다음 visited에 들어갈수있는 수 가 있는지 check

        visited.pop();
        //체크하고난 후 빠져나올 땐 visited에서 pop(가장 최근의것이 pop됨 Queue)
      }
    }
  };

  dfs();

  return answer;
}
solution(n, k);