[Programmers] 2019 카카오 인턴십 5번 - 징검다리 건너기

[문제 설명]

징검다리가 있다.

각 디딤돌은 밟을 수 있는 숫자가 적혀 있다.

디딤돌의 숫자가 0이 되면 그 다음 가까운 디딤돌로 건널 수 있다.

문제에서 한 번에 건널 수 있는 최대 디딤돌의 수 (k) 가 주어진다.

주어진 디딤돌 상태에서 최대 몇 명까지 징검다리를 건널 수 있는지를 구하는 문제.

 

[조건]

1 <= len (stones) <= 200,000

1 <= stones 배열의 각 원소값 <= 200,000,000

 

[풀이]

디딤돌에 적힌 숫자가 저장된 stones 배열을 오름차순으로 정렬한다.

그러면 최솟값이 첫 번째 원소가 되는데, k 값과 상관 없이 최솟값만큼의 친구가 건널 수 있다.

 

그러나, 문제는 한 번에 건널 수 있는 디딤돌 수 k가 주어졌다는 점이다.

이 때문에, k개가 연속으로 0인지 아닌지가 중요해진다.

정렬을 해버리면, 이 정보를 파악하기가 힘들다.

 

따라서 이 문제는 정렬하는 것이 아니라, 최솟값을 설정하고, 해당 최솟값이 조건에 만족하는지 찾는 방법을 써야한다.

 

public class Programmers_kakao2019_intern_5 {
	static final int maximumStep = 200000000;
	static final int minimumStep = 1;
	
	public static int solution(int[] stones, int k) {
		int answer = 0;
		
		int left = maximumStep + 1;
		int right = minimumStep - 1;
		int mid = 0;
		
		// 최대값 : right, 최소값 : left 
		for (int s = 0; s < stones.length; ++s) {
			left = (left < stones[s]) ? left : stones[s];
			right = (right > stones[s]) ? right : stones[s];
		}
		
		search : while (left <= right) {
			mid = (left + right) / 2;
			
			int idx = 0;
			int count = 0;
			
			while (idx < stones.length) {
				if (stones[idx++] < mid) {
					count++;
				}
				else {
					count = 0;
				}
				
				if (count >= k) { // mid 이하인 디딤돌이 k개 연속되는 경우 실패
					right = mid - 1;
					continue search; 
				}
			}
            
            // 그 외의 경우 성공
			left = mid + 1;
			answer = mid;
		}
		return answer;
	}	
	public static void main(String[] args) {
		System.out.println((solution(new int[] {2, 4, 5, 3, 2, 1, 4, 2, 5, 1}, 3)));
	}
}

 

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

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