[CodeKata] 프로그래머스: 10.31(일), 징검다리 건너기

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

위 로직을 그대로 while 반복문으로 구현한 풀이이다. 정확성은 만점이나, 효율성에서 모두 초과가 발생하여 모범답안을 탐구했다!

function solution(stones, k) {
  var answer = 0;
  
  while (true) {
    answer++;
    stones = stones.map(stone => Math.max(stone-1, 0));
    idx = stones.findIndex(s => s === 0);
    while (idx !== -1) {
      const jump = stones.slice(idx+1,idx+k);
      if (jump.length === k-1 && !jump.find(stone => stone !== 0)) {
        return answer
      }
      idx = stones.findIndex((s,i) => i > idx && s === 0);
    }
  }
}

• answer로 건넌 사람수를 센다. 1을 더하며, 이 때 건넜다는 가정하에 stones의 모든 돌을 -1 한다. (음수가 될 경우 0으로)
• stones의 모든 0인 구간을 idx로 지정한다. 이 때, jump(idx 다음부터 k칸 내의 징검다리들)를 stones 에서 가져온다.
• 이 jump의 길이가 k-1 길이와 같으면서, 0이 아닌 징검다리를 포함하지 않는다면 건너지 못하는 조건이다. 이 때, answer가 건널 수 있는 사람의 최대치이므로 이를 반환한다.

 

🖇 리뷰

이중for문은 모두 시간초과가 발생하여, 이분탐색으로 풀이한 모범답안이 많았다.

function checkStone(stones, mid, k) {
    let now = 0; // 몇개가 연속으로 0 미만이 되었는지
    for(let i = 0; i < stones.length; i++) {
        if(stones[i] < mid) { // mid가 더 크면 stones[i] - mid 가 0보다 작다는 소리다. 그러면 마지막 사람이 지나가기 전에 돌이 0이 됐다는 소리다.
          // 만약 딱 0이라면 자신이 지나가고 나서 0이 되므로 지나갈 수 있다는 소리.
            now += 1;
        }
        else { // 지나갈 수 있을 땐 연속으로 못 지나가는게 초기화 됨.
            now = 0;
        }
        if(now >= k) { // 연속으로 못 지나가는 개수가 k보다 크거나 같으면 통과 못 하는 것.
            return false;
        } 
    } 
    
    return true;
}
function solution(stones, k) {
    let left = 1; // 최소, 최대값
    let right = 200000000;

    while(left < right-1) {
        let mid = parseInt((left + right) / 2);
        if (checkStone(stones, mid, k)) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left;
}

* 출처 : https://velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level3-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0-JavaScript  

1. checkStone() 함수

• 현재 탐색값(mid) 수만큼 사람이 지나갈 수 있는지 판정하는 함수이다. 인자는 기존의 stones, k 와 mid 세가지를 받는다.
• mid값을 기준으로, stones를 for문 순회하며 탐색한다. 이 때, 못 건너는 돌의 개수를 now 변수에 누적하는 것이다.
• 현재 돌(stones[i])이 mid값보다 작다면 해당 수만큼 사람이 지나갈 수 없다. 이 때는 now에 +1을, 아니라면 0으로 초기화한다.
• 만약, now가 제한개수인 k개 이상이 되는 경우는 통과를 못하는 것이다. 이 때는 false를, 모두 통과가 가능하다면 true를 반환한다.

 

2. solution() 풀이함수

• 이분탐색의 left(최소값) / right(최대값)을 설정한다. stones 원소 최소값인 1, 최대값인 200,000,000 으로 각각 설정한다.
• left가 right보다 작은동안에 while 반복문을 반복하며 탐색한다. mid는 현재 left, right의 중간값이다.
• 이를 checkStone() 함수를 통해 판정한다. 통과가 가능하다면 left를 mid로 올려서, 불가능하다면 right를 내려서 재탐색한다.
• 이분탐색이 종료가 되면, left 값이 통과할 수 있는 최대 사람수가 되어있다. 이를 최종적인 정답으로 반환한다.

 

지난 "금과 은 운반하기" 문제도 그렇고, 이분탐색이 생각보다 사용할 수 있는 범주가 많음을 느꼈다.

조건이 만족했을 때, left 값을 mid로 올리면 최대값을, right 값을 mid로 내리면 최소값을 추적할 수 있는 좋은 기법인 것이다.