[프로그래머스] 징검다리 건너기 : 2019 카카오 개발자 겨울 인턴십 - 자바(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

문제 해석

징검다리는 일렬로 놓여 있으며 디딤돌에는 숫자가 적혀 있다.

 

디딤돌의 숫자는 한번 밟을 때 마다 1씩 줄어든다.

 

디딤돌의 숫자가 0이되면 더 이상 밟을 수 없다.

 

그렇게 되면 그 다음 디딤돌로 한번에 여러 칸을 건너 뛰어 가야한다

 

단, 다음으로 밟을 수 있는 디딤돌이 여러개면 무조건 가장 가까운 디딤돌로만 뛸 수 있다.

 

한번에 건너 뛸 수 있는 디딤돌의 최대 칸수 k가 주어지기 때문에 만약 다음 디딤돌까지의 거리가 k이상이라면 더 이상 건널 수 없다.

 

여러명이 징검다리를 건너야 하는데 최대 몇명까지 징검다리를 건널 수 있을 까?

징검다리 사진 예시

문제 풀이 전 설계

가장 떠올리기 쉬운 방법은 차례대로 한명씩 보내면서 stone의 count를 깎는것입니다.

하지만 stones 배열의 크기가 20만이기 때문에 O(N^2)으로 설계하면 시간초과가 발생할 것 같습니다.

 

징검다리를 건널 수 있는 사람의 수를 이진탐색으로 해결해야하는 문제였습니다.

 

문제 풀이

 

초기값 설정

int result = 0;
int min = 1;
int max = 200_000_000

징검다리를 건너는 친구의 수

징검다리를 건너는 친구의 최소 수

징검다리를 건너는 친구의 최대 수를 설정합니다.

 

문제의 조건중 다음과 같은 조건을 통해 위와 같은 값을 세팅

• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

이분탐색

       // 이분탐색 할 기준 : 징검다리는 건널 수 있는 친구의 수
        while (min <= max) {
          	// 징검다리를 건널 인원
            int mid = (min + max) / 2;
            
            // 징검다리 건널 수 있는지 확인
            if (canAcrossRiver(stones, k, mid)) {
              	// 다리를 건널 수 있으면 더 많은 친구들이 가능한지 친구의 수를 넓힘
                min = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                // 다리를 건널 수 없으면 친구의 수를 좁힘
                max = mid - 1;
            }
        }

 

 

다리건너기

    boolean canAcrossRiver(int[] stones, int k, int friends) {
        // 못 건너는 징검다리의 개수를 저장
      	int skip = 0;
        
        for (int stone : stones) {
            // 디딤돌의 숫자 - 건너는 친구의 수
            if (stone - friends < 0)
              	// 0보다 작으면 건널 수 없음을 의미
                skip++;
            else
              	// 0 이상이면 건널 수 있음의 의미 = 이 지점에 위치하면 다음으로 갈 수 있음
                // 다시 0으로 갱신
                skip = 0;
            
            // 못 건너는 징검다리의 수가 최대칸 k를 넘으면 해당 값은 건널 수 없음을 의히
            if (skip == k)
                return false;
        }
        
        return true;
    }

 

 

코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
      	// 징검다리를 건너는 친구의 최소 수
        int min = 1; 
        // 징검다리를 건너는 친구의 최대 수
        int max = 200000000;
	      
        // 이분탐색 할 기준 : 징검다리는 건널 수 있는 친구의 수
        while (min <= max) {
          	// 징검다리를 건널 인원
            int mid = (min + max) / 2;
            
            // 징검다리 건널 수 있는지 확인
            if (canAcrossRiver(stones, k, mid)) {
              	// 다리를 건널 수 있으면 더 많은 친구들이 가능한지 친구의 수를 넓힘
                min = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                // 다리를 건널 수 없으면 친구의 수를 좁힘
                max = mid - 1;
            }
        }
        
        return answer;
    }
    
    boolean canAcrossRiver(int[] stones, int k, int friends) {
        // 못 건너는 징검다리의 개수를 저장
      	int skip = 0;
        
        for (int stone : stones) {
            // 디딤돌의 숫자 - 건너는 친구의 수
            if (stone - friends < 0)
              	// 0보다 작으면 건널 수 없음을 의미
                skip++;
            else
              	// 0 이상이면 건널 수 있음의 의미 = 이 지점에 위치하면 다음으로 갈 수 있음
                // 다시 0으로 갱신
                skip = 0;
            
            // 못 건너는 징검다리의 수가 최대칸 k를 넘으면 해당 값은 건널 수 없음을 의히
            if (skip == k)
                return false;
        }
        
        return true;
    }
}

 

 

 

출처

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

[프로그래머스/640464] 징검다리 건너기 (Java)