문제풀이/프로그래머스
[프로그래머스]징검다리 건너기 - JAVA
빈둥벤둥
2021. 2. 21. 13:41
[프로그래머스]징검다리 건너기
programmers.co.kr/learn/courses/30/lessons/64062
코딩테스트 연습 - 징검다리 건너기
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3
programmers.co.kr
풀이
이분탐색 문제이다! 이분탐색을 하지 않고 풀면 시간초과가 날 것이다!
전형적인 이분탐색의 유형으로 최소값, 최대값을 건널 수 있는 프렌즈의 수 범위로 둔다. 처음에는 min을 0, max를 건널 수 있는 프렌즈의 최대값으로 둔 다음, mid이상의 프렌즈가 건널 수 있다면 min을 mid + 1로, mid이상의 프렌즈가 건널 수 없다면 max를 mid - 1로 변경하여 또 탐색한다.
이때 건널 수 있는지 없는지 판단하는 방법은 간단하다. stones의 각 요소가 mid보다 작은지만 판단하면 된다. 그리고 작을때는 count변수를 사용해 작은 stones의 연속적인 개수를 세어주고 count가 k와 크거나 같아지는 순간 건널 수 없는 상태가 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public int solution(int[] stones, int k) {
int min = 0;
int max = Integer.MAX_VALUE;
int result = 0;
while(min <= max) {
int mid = (min + max) / 2;
if(check(mid, k, stones)) {
min = mid + 1;
result = mid;
} else {
max = mid - 1;
}
}
return result;
}
public boolean check(int mid, int k, int[] stones) {
int count = 0;
for(int i = 0; i < stones.length; i++) {
if(stones[i] < mid) { //mid보다 작으면 mid가 건널 수 없다.
count++;
if(count >= k) return false;
} else count = 0;
}
return true;
}
}
|
cs |