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

문제

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

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

설명

제한 사항을 보면 stones 배열의 크기는 1 이상 200,000 이하, stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수이다.

한 명 한 명 징검다리를 건너 보내면서 총 몇 명이 징검다리를 건널 수 있는지 확인한다면 굉장히 많은 시간이 걸림.

시간 초과가 나서 효율성에서 탈락함ㅠㅠㅠ 시간을 줄일 방법을 생각해서 문제를 풀어야 한다.

 

1. 이진 탐색으로 풀이

이진 탐색을 이용해 탐색의 시간을 줄이자!

 

* 이진 탐색과 관련된 포스트는 아래를 확인해주세요!

 

이진 탐색 = 이분 탐색 (Binary Search) - Java로 구현

1. 이진 탐색을 위해 먼저 low, high, mid값을 설정하자.

int low = 1; // stones 원소의 최소값 
int high = 200000000; // stones 원소의 최대값
int mid = 0; // 추후에 (low + high) / 2 해줄 것 
int answer = 0;

 

• low : stones 배열의 최솟값인 1
• high :  stones 배열의 최댓값인 200, 000, 000
• mid : (low + high) / 2

2. 구해진 mid값 (= 징검다리를 건널 인원)으로 징검다리를 건널 수 있는지 없는지를 확인하자.

이 과정은 corss 함수에 구현했다.

 

// 현재 mid 값(인원)으로 징검다리를 건널 수 있는지 없는지 확인 
public static boolean cross(int[] stones, int k, int mid) {
	int cnt = 0;

	for (int stone : stones) {
		if (stone - mid < 0) { // 0보다 작아서 못 건너가면 cnt++
			cnt++;
		} else {
			cnt = 0; // 0이상이면 건너갈 수 있음 - cnt 0으로 다시 갱신 
		}

		// 못 건너서 쌓인 cnt의 값이 건널 수 있는 최대칸 수 k를 넘으면 현재 mid 값으로는 건널 수 없음 
		if (cnt == k) 
			return false;
	}

	return true; // 다 통과하면 건널 수 있음 
}

 

전체 디딤돌을 순회하며, 디딤돌이 가진 값에서 mid값(즉 징검다리를 건널 인원)을 뺀다.stones [i] - mid

 

• 값이 0보다 작다면 건너갈 수 없기에 cnt 변수를 +1 해준다.
• 값이 0보다 크다면 건너갈 수 있기에 cnt 값을 다시 0, 초기값으로 만들어준다.

만약 건너가지 못하고 ++된 cnt 값이 k값(최대로 건널 수 있는 값)과 같아진다면,

현재 mid값으로는 건널 수 없음을 의미하기에 false를 반환한다.

 

하지만 마지막 디딤돌까지 false를 반환하지 않고 확인했다면, 현재 mid값으로 건널 수 있으므로 true를 반환한다.

 

3. 건널 수 있는지 없는지를 판별을 했다면 low와 high을 조정해 범위를 줄이자.

 

while(low <= high){
	mid = (low + high) / 2; // 중간값 

	// 중간값으로 건널 수 없다는 것은 중간보다 큰 값은 모두 건널 수 없다는 의미 -> 중간-1 값부터 다시 확인 
	if(!cross(stones, k, mid)) {
		high = mid - 1; 
	} else { // 중간값으로 건널 수 있다는 것은 중간보다 작은 값은 모두 건널 수 있다는 의미 -> 중간+1 부터 다시 확인 
		low = mid + 1; 
		answer = Math.max(answer, mid); // 최대 mid 값을 가진 answer인 경우만 값 갱신 
	}
}

return answer;

 

cross 함수에서 false가 반환되어 징검다리를 건널 수 없다면

중간 값보다 큰 값들로는 징검다리를 건널 수 없다는 것을 의미한다.

따라서 중간보다 작은 값의 인원으로 징검다리를 건널 수 있는지 없는지를 다시 확인해야 하기에 high를 mid -1로 바꿔준다.

 

하지만 true가 반환되어 징검다리를 건널 수 있다면

중간 값보다 작은 값들로는 징검다리를 모두 건널 수 있다는 것을 의미한다.

따라서 중간보다 큰 값의 인원으로 징검다리를 건널 수 있는지 없는지를 다시 확인해야 하기에 low값을 mid+1로 바꿔준다.

 

추가로 건널 수 있을 경우 최대의 answer값인지는 모르겠지만, answer가 될 가능성이 있다.

따라서 Math.max로 answer값을 바꿔준다.

전체 코드 1

import java.util.Arrays;

class Solution {

public static int solution(int[] stones, int k) {
		int low = 1; 
		int high = 200000000; 
		int mid = 0;
		int answer = 0;

		while(low <= high){
			mid = (low + high) / 2; 

			if(!cross(stones, k, mid)) {
				high = mid - 1; 
			} else {
				low = mid + 1; 
				answer = Math.max(answer, mid); 
			}
		}

		return answer;
	}
	
	public static boolean cross(int[] stones, int k, int mid) {
		int cnt = 0;

		for (int stone : stones) {
			if (stone - mid < 0) { 
				cnt++;
			} else {
				cnt = 0;
			}

			if (cnt == k) 
				return false;
		}

		return true; 
	}
}

2. 이진 탐색을 응용한 파라메트릭 서치를 활용한 풀이 

파라메트릭 서치라는 걸 이문제를 풀면서 처음 알게 되었다.

이진 탐색이랑 비슷하긴 한데 정답이 되는지 아닌지를 결정한다는 점에서 조금은 차이가 있다고 한다.

 

요약하자면, 파라메트릭 서치는 이진 탐색과 다르게 주어진 일련의 값들이 아니라

주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이라고 한다.

 

예를 들어 이진 탐색이 1부터 9까지의 값 중에서 3이라는 값을 찾는 알고리즘이라면

파라메트릭 서치는 1부터 9까지의 범위 내에서 3이라는 값을 찾아나가는 것이라는 차이가 있다고 한다.

마치 3 자체를 찾는 게 아니라 3보다 크거나 작은 어떠한 값을 찾기 위해 3을 찾아나가는...?

사실 잘 모르겠다 ^_____ㅠ

 

아래 포스트를 참고해보자!

 

파라메트릭 서치 관련 포스트 

 

아무튼 이 파라메트릭 서치를 활용해 위에서 푼 것보다 좀 더 효율적으로 문제를 풀 수 있다!

위의 1번 코드는 최솟값과 최대값을 1과 200,000,000 으로 준뒤 풀었다.

하지만 이번 코드에서는 최소값과 최댓값을 먼저 찾은 뒤에 이진 탐색을 이용해 문제를 풀 것이다.

 

먼저 징검다리를 건널 수 있는 인원의 최솟값은 stones(디딤돌 숫자 담고 있음) 배열의 값 중 최솟값,

최댓값은 stones 배열의 값 중 최댓값과 같다.

 

 

예제를 기준으로 설명하자면 최솟값은 1, 최댓값은 5이다.

최소 1명은 건너갈 수 있고, 다른 디딤돌의 상황에 따라 최대 5명까지도 건너갈 수 있다는 뜻이다.

따라서 이 최솟값과 최댓값을 low와 high 값으로 이진 탐색을 시작한다. (low = 1, high = 5)

 

이진 탐색을 하며 low와 high의 중간값인 mid값의 인원으로 징검다리를 건널 수 있는지 없는지를 확인한다.

(mid = (low + high) / 2 = 3)

 

만약 mid값으로 징검다리를 건널 수 있다면, 그보다 작은 값의 인원으로는 징검다리를 모두 건널 수 있다는 것을 의미한다.

그렇기에 mid + 1 값부터 다시 확인한다.

 

하지만 mid값으로 징검다리를 건널 수 없다면, 그보다 큰 값의 인원으로는 모두 건널 수 없다는 것을 의미한다.

따라서 mid-1   값부터 다시 확인한다.

 

이런 식으로 이진 탐색을 반복하며 건널 수 있는 최대 인원을 구하면 된다.

 

* 징검다리를 건널 수 있는지 아닌지를 확인하는 cross 함수는 1번 코드에서 설명한 것과 동일하다.

 

* 전체 코드 2의 parametricSearch와 parametricSearch2의 차이 

이 둘의 차이는 중간값 mid를 구할 때 반올림을 했냐 안했냐의 차이이다.

 

범위가 클 때는 상관없지만 범위가 1~2처럼 1 차이를 가지는 경우, 나누기 2를 했을 때 반올림을 해주냐 안 해주냐의 차이 정도다.

둘 중에서 원하는 코드로 쓰면 된다.

(블로그 여기저기 찾아보다가 왜 비슷한데 코드가 다르지? 했는데 그냥 반올림의 문제였음)

 

1. mid = (low + high) / 2

(1 + 2) / 2 = 1.5

 

2. mid = (low + high + 1) / 2

(1 + 2 + 1) / 2 = 2

전체 코드 2

import java.util.Arrays;

class Solution {
public static int solution(int[] stones, int k) {
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		// 디딤돌 수의 최대값, 최소값 구함 
		for(int n : stones) {
			max = Math.max(max, n); 
			min = Math.min(min, n); 
		}

		return parametricSearch(stones, k, min, max);
	}

	public static int parametricSearch(int[] stones, int k, int low, int high) {
		if(low == high) // 최소값, 최대값이 같다면 그 값으로 건널 수 있으니 확인할 필요 없음 
			return low;

		while(low < high) {
			// +1 하면 mid가 1.5가 나올시 2가 되는 경우
			int mid = (low + high + 1) / 2; 

			if(cross(stones, k, mid)) { 
				low = mid;
			} else {
				high = mid - 1;  
			}
		}

		return low; // or return high;
	}

	public static int parametricSearch2(int[] stones, int k, int low, int high) {
		if(low == high) 
			return low;

		while(low < high) {
			// mid가 1.5가 나올시 1이 되는 경우 
			int mid = (low + high) / 2; 

			if(cross(stones, k, mid)) { 
				low = mid + 1;
			} else {
				high = mid; 
			}
		}
        
		// cross의 반환값이 true일 때, 다음 mid 가능한지 확인하기 위해서 +1 했으니 리턴할 땐 -1해서 반환 
		return high-1; 
	}

	public static boolean cross(int[] stones, int k, int mid) {
		int cnt = 0;

		for (int stone : stones) {
			if (stone - mid < 0) { 
				cnt++;
			} else {
				cnt = 0; 
			}

			if (cnt == k) 
				return false;
		}

		return true;
	}
}

 

GITHUB

github.com/KwonMinha/Programmers/tree/master/2019_Kakao_Blind_Recruitment/src

KwonMinha/Programmers