프로그래머스 level3)징검다리 건너기

링크 : 프로그래머스 level3)징검다리 건너기

풀이

처음에는 StringBuilder로 k개수로 0을 String 형태로 만들었다.
그래서 stones 배열을 -1한다. 그리고 그 배열을 String 형태로 만들고
k개수로 만든0을 contain하고 있는지 확인하는 형식으로 했다.
결과는 정확성도 몇개 틀리고, 효율성은 모두 실패

두번째 방법은 contain이 시간을 많이 잡아먹는건가라는 생각에 배열을 -1하면서
0이 연속해서 k번 나올때 반복문을 나온다.
결과는 정확성은 다 맞았는데, 효율성은 모두 실패

class Solution {
    public int solution(int[] stones, int k) {
       		int answer = 0;
		while(true){
			int temp_num = 0;
			for (int i = 0; i < stones.length; i++) {
				if (stones[i] != 0) {
					stones[i] -= 1;
					if(i!=0 &&stones[i-1]==0)
						temp_num=0;
				} else if (stones[i] == 0)
					temp_num++;
                    
				if(temp_num==k)
				    return answer;
			}
			answer++;
		}
    }
}

모두들 효율서을 성공하려면 이분탐색을 해야한다고 하지만
나는 이분탐색을 어떻게 이 문제에 적용해야할지 몰라
다른 분 풀이를 참고 했다.

int[] stones = { 2, 4, 5, 3, 2, 1, 4, 2, 5, 1 };
int k = 3;
이 예시에서 디딤돌의 최소값은 1이고 최대값은 5이다.
여기서 이 두 값 사이의 값은 3이다.
과연 3명으로 디딤돌을 건널수있을까?
stones 배열의 값을 순서대로 3으로 뺀다.
3으로 뺐을때 0보다 아래이면 count++한다.
중간에 0이 아니라면 count는 0으로 초기화

count가 k와 같은지 여부를 체크해준다.
같다면 false리턴

이때 true를 return 한다.
-1, 1, 2, 0, -1, -2, 1, -1, 2, -2 이기 떄문이다.
이것은 몇명 더 건널수있다는 말이다.
min=mid로 바꿔준다.

이제는 min: 3 mid: 4 max: 5 이다.
과연 4(mid)명으로 디딤돌을 건널수있을까?
-2,0, 1,-1, -2, -3, 0,-2, 1, -3임으로
이때 false를 리턴한다.
max = 4 - 1;
max = 3;
min: 3 max: 3
이때 while문 조건 에 걸리기 때문에 max값이 return 한다.

public class Main {
	public static void main(String[] args) {

		int[] stones = { 2, 4, 5, 3, 2, 1, 4, 2, 5, 1 };
		int k = 3;

		System.out.println("answer=" + solution(stones, k));
	}

	public static int solution(int[] stones, int k) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int stone : stones) {
			min = Math.min(min, stone);
			max = Math.max(max, stone);
		}

		while (min < max) {
			int mid = (min + max + 1) / 2;
			System.out.println("min: "+min+" mid: "+mid+" max: "+max);
			// 조건을 만족하는가
			if (isPossible(mid, k, stones)) {
				// 예
				min = mid;
			} else {
				// 아니요
				max = mid - 1;
			}
		}
		return max;
	}

	public static boolean isPossible(int num, int k, int[] stones) {
		int count = 0;
		for (int stone : stones) {
			if (stone - num < 0) {
				count++;
			} else {
				count = 0;
			}

			if (count == k) {
				return false;
			}
		}
		return true;
	}
}