쌓고 쌓다
[프로그래머스] 징검다리 건너기 Java 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/64062
풀이 방법
0명부터 200000000명을 이분탐색을 통해 n명이 이 다리를 건널 수 있는지 탐색하면 된다.
어떻게 풀지 전혀 모르겠는데 검색해보고 이렇게 이분탐색을 사용해서 문제를 푸는구나 신기했다...
전체 코드
class Solution {
public int solution(int[] stones, int k) {
int answer = 0;
int start = 0;
int end = 200000000;
while(start<=end) {
int mid = (start + end) / 2;
if(isAble(stones, k, mid)) {
answer = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return answer;
}
// stones를 n명이 건널 수 있는가
boolean isAble(int[] stones, int k, int n) {
int cnt = 0;
for(int i=0; i<stones.length; i++) {
if(stones[i] < n)
cnt++;
else
cnt=0;
if(cnt==k)
return false;
}
return true;
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드 Java 풀이 및 해설 (1) | 2024.05.15 |
---|---|
[프로그래머스] 섬 연결하기 Java 풀이 및 해설 (0) | 2024.05.14 |
[프로그래머스] 보석 쇼핑 Java 풀이 및 해설 (0) | 2024.05.13 |
[프로그래머스] 불량 사용자 Java 풀이 및 해설 (0) | 2024.05.11 |
[프로그래머스] 스티커 모으기(2) Java 풀이 및 해설 (0) | 2024.05.09 |
Comments