티스토리 뷰
728x90
https://school.programmers.co.kr/learn/courses/30/lessons/64062
2019 카카오 개발자 겨울 인턴십 Level 3 문제다.
문제 설명에 나온 입출력 예시 처럼
무식하게 while문을 통해 징검다리를 1씩 감소시키는 방식으로 풀었었는데,
당연히 시간초과가 났다.
알고리즘을 풀면서 이분탐색을 많이 사용해본적이 없어서
어떤 문제에 이분탐색을 사용해야 하는지 캐치하지 못했던 것 같다.
결국 다른 분의 풀이를 참고했다.
어떤 징검다리를 4명이 건널 수 있다면,
징검다리의 값에서 1씩 4번 감소시키며 건널 수 있는지 확인하는 것과
아예 4를 한번 감소시켜 건널 수 있는지 확인하는 것과 동일하다. (당연하지만 생각해내지 못함...)
건널 수 있는 최소 인원과 최대 인원을 설정한 후 중간값을 구하고,
그 중간값이 다리를 건널 수 있다면 최소 인원을 증가,
건널 수 없다면 최대 인원을 감소시키고
최소 인원과 최대 인원이 엇갈릴 때까지 반복한다.
class Solution {
public int solution(int[] stones, int k) {
int ans = 0;
int min = 1, max = 200000000;
while(min<=max) {
int mid = (min + max) / 2;
if(isToCross(mid, stones, k)) {
ans = Math.max(ans, mid);
min = mid + 1;
}
else
max = mid - 1;
}
return ans;
}
static boolean isToCross(int people, int[] arr, int k) {
int num = 0;
for(int i : arr) {
if(i - people < 0)
num++; // 밟지 못하는 칸이 얼만큼 연속되는지 카운트
else
num = 0;
if(k == num) // 한 번에 건널 수 있는 칸과 같으면 못 건너는 것
return false;
}
return true;
}
}
참고
728x90
'algorithm > programmers' 카테고리의 다른 글
[프로그래머스/자바] 수식 최대화 풀이 - 2020 카카오 인턴십 (0) | 2022.11.13 |
---|---|
[프로그래머스/자바] 키패드 누르기 풀이 - 2020 카카오 인턴십 (0) | 2022.11.13 |
[프로그래머스/자바] 튜플 풀이 - 2019 카카오 개발자 겨울 인턴십 (0) | 2022.11.13 |
[프로그래머스/자바] 불량 사용자 풀이 - 2019 카카오 개발자 겨울 인턴십 (0) | 2022.11.13 |
[프로그래머스/자바] 크레인 인형뽑기 게임 - 2019 카카오 개발자 겨울 인턴십 (0) | 2022.11.13 |