[프로그래머스] 징검다리 (JS/javascript) - 매우쉬운풀이

알고리즘 문제를 풀다 보면 "이건 무슨 소리야?" 싶은 설명을 자주 만나게 됩니다. 문제 자체보다 문제를 읽는 거 자체가 일인 경우가 종종 있습니다.

 

오늘은 "[징검다리]" 문제를 동네 옆집 아저씨도 이해할 수 있을 정도로 쉽게 풀어보겠습니다. 복잡한 용어는 빼고, 직관적인 예제로 천천히 설명해볼 테니 부담 없이 따라와 주세요! 🚀

 

어쩌면 세상에서 가장 쉬운 알고리즘 풀이 입니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/43236

 

문제는 위와 같습니다. 그럼 이 문제에 대해서 아주 쉽게 설명해보겠습니다.

 

문제 파악

 

1. 강 건너기 게임

 

상상해보세요 강 건너편에 도착하려면 0 에서 시작해서 도착지(예를들어 25)까지 가야됩니다. 강 중간 중간에는 돌들이 여기저기 있는 상황입니다.

 

2. 목표

• 큰 발걸음 걷기 : 여러분은 한 걸음 한 걸음이 너무 작으면 불편하니깐, 가능한 한 큰 발걸음(돌 사이의 간격)을 만들고 싶습니다.
• 제한 : 하지만 돌을 몇개 제거할 수 있는지 횟수가 정해져있습니다. 예를들어, 최대 2개만 제거할 수 있다고 생각해봅시다.

 

3. 문제의 핵심

 

강을 건너는데, 돌들 사이의 가장 작은 간격이 최대값이 되도록(즉, 한 걸음 한 걸음이 모두 넓어지도록) 돌들을 제거할 수 있을까? 라는 질문입니다.

 

어떻게 풀어야 되나?

 

1. 돌들의 순서 맞추기(정렬)

• 먼저 돌들이 강 위에 위치한 순서대로 배열되어야 합니다. 문제의 예로 들면 돌들이 [2, 14, 11, 21, 17]이라면 이걸 오름차순으로 [2, 11, 14, 17, 21]로 정렬해야됩니다.
  이렇게 해야 0에서 2, 2에서 11, 11에서 14, ... 이렇게 순서대로 걸음을 계산할 수 있어

 

2. 이정도 간격이면 괜찮을까 하고 물어보기

• 여러분이 내 발걸음 간격이 4라면 괜찮을까 라고 가정해봅니다.
• 0에서 첫 번째 돌까지 4 이상 떨어져있어야 하는데, 만약 0에서 2는 4보다 작으니 이 돌은 제거해봅니다.
• 그 다음 돌과의 거리를 계속 확인하면서, 만약 두 돌사이의 거리가 4 미만이면 그 돌을 제거하는 방식입니다.
• 마지막 도착지까지의 간격도 4 이상이어야 합니다.
• 제거한 돌의 개수가 허용된 범위(예: 2개) 이하면 " 네, 4의 간격으로 갈 수 있어요!" 라고 판단할 수 있습니다.

 

3. 최적의 간격 찾기(이분탐색)

• 이분탐색은 "숫자 맞추기 게임" 입니다.
  
  • 예를 들어, 발검음 간격을 1부터 25까지 찾아야 된다고 가정합니다.
  • 중간값 13을 먼저 시도하고 13의 간격으로 갈 수 있는지 확인합니다.
  • 13이 너무 크다면 간격을 줄여보고, 가능하면 더 크게 해봅니다.
  • 이 과정을 반복해서, "이렇게 최대한 크게 만들 수 있는 간격은 얼마일까?"를 찾는것입니다.

 

정리하자면

 

목표 : 강을 건널 때, 한 걸음(돌 사이의 간격) 이 너무 작지 않게 최대한 넓게 만들고 싶다.

방법 : 
1. 돌들을 순서대로 정리

2. 이정도 간격이면 가능할까? 라고 확인하면서 돌들을 제거할 수 있는지 확인(제거 갯수제한 조건이 넘지않도록)

3. 가능한 간격 중에서 가장 큰 값을 찾기 위해 이분탐색 사용

여기서 이분탐색 자체의 개념이 흔들리는 분들을 위한 정리

 

숫자 맞추기 게임으로 비교 해봅시다.

 

1. 상황설정 : 

• 1부터 25까지의 숫자 중에서 어떤 비밀숫자를 찾는 게임이 있다고 생각해봅시다.

 

2. 첫번째 추측 : 

• 그냥 1씩 다 일일이 물어보는 대신 중간 숫자인 13을 먼저 물어봅니다.

 

3. 답에 따른 행동 : 

• 만약 13보다 정답 숫자가 크다고 하면 범위를 14 ~25로 좁힙니다.
• 반대로 13이 너무 크다고 하면 범위를 1부터 12까지로 좁힙니다.

 

4. 반복 : 

• 이렇게 매번 중간 숫자를 선택하면서 범위를 계속 반으로 좁혀 나가면, 결국 정답 숫자를 빠르게 찾을 수 있습니다.

 

징검 다리 문제에 이 내용을 추가해보면

• 우리는 돌 사이의 간격을 최대로 만드는 값을 찾으려는 것입니다.
• 가능한 간격의 범위가 1부터 강의 전체 길이 까지 있다고 생각합니다.
• 이 중에서 중간값을 선택해서 이 간격이면 강을 건널수 있을까 라고 테스트 합니다.
  • 만약 너무 크면 돌들을 많이 제거해야되서 안되고, 너무 작으면 조건은 맞지만 더 큰 간격을 시도해볼 수 있으니 범위를 조정합니다.
• 이렇게 반복해서 최종적으로 돌 사이 간격의 최대값을 찾는 것이 바로 이분탐색입니다.

 

전체 소스 코드 

function solution(distance, rocks, n) {
    var answer = 0;
    
    // 1. 돌의 위치를 오름차순으로 정렬
    rocks.sort((a,b)=>a-b);
    
    // 2. 간격 판단 함수: 주어진 간격(mid)을 만족할 수 있는지 판단
    const canOver = (mid) => {
        let removed = 0; //제거한 돌의 수
        let prev = 0; //마지막으로 밟은 돌의 위치(시작점은 0)
        
        for(let rock of rocks){
            if(rock - prev < mid){
                // 현재 돌과 prev 사이의 거리가 mid보다 작으면, 돌을 제거합니다.
                removed ++ ;
            }else{
                // 간격이 충분하면 이 돌을 유지하고 prev를 갱신합니다.
                prev = rock;
            }
        }
        
        // 마지막으로, 도착점과 마지막 돌 사이의 간격을 확인합니다.
        if(distance - prev < mid) removed ++;
        return removed <= n;
    }

    // 3. 이분 탐색: 가능한 간격의 범위는 1부터 distance까지
    let start = 1;
    let end = distance;
    
    while(start <= end){
        let mid = Math.floor((start +end)/2);
        
        if(canOver(mid)){
            // mid 간격이 가능하면, answer를 갱신하고 더 큰 값을 시도합니다.
            answer = mid;
            start = mid+1;
        }else{
            // mid 간격이 불가능하면, 더 작은 값을 시도합니다.
            end = mid-1;
        }
    }
    
    return answer;
}

이해가 잘 되셨을지 모르겠습니다. 저는 기초가 많이 흔들려있었기 때문에 이렇게 쉽게까지 풀어쓰지 않으면 이해조차 힘들었던 시기가 있었기 때문에 저의 과거처럼 기초가 많이 흔들리시는 분들을 위해 하나하나 풀이 해 나가도록 하겠습니다.

알고리즘 풀이 반박시 니말이 다 맞음.