🔗 문제 링크
[프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십
📝 풀이 과정
돌의 최솟값을 기준으로 이분탐색하는 방법을 사용했다. 범위는 돌의 크기인 1 ~ 200,000,000으로 지정해주었다.
N-1번 니니즈까지 길을 건넜다고 가정하고 N번째 니니즈가 길을 건너는 차례라고 생각한다. K번 이내의 거리에 N이상의 값이 존재해야 길을 건널 수 있기 때문에 N미만의 값이 연속적으로 k개 이상 나온다면 길을 N번은 건널 수 없다는 의미가 된다.
따라서 범위를 줄여주고 다시 탐색을 시작해주고, 만약 연속 값이 k보다 작다면 길을 건널 수 있는 경우로 값을 저장한 값을 늘려 다시 탐색을 진행하였다.
⏱ 시간 복잡도
이분탐색의 시간 복잡도는 $O(\log({2\times 10^8}))$이다.
탐색할 때마다 선형으로 돌을 탐색해야 하기 때문에 최종 시간 복잡도는 $O(n\times\log({2\times10^8}))$
💻 코드
public class Solution {
public int solution(int[] stones, int k) {
int start = 1, end = (int) (2 * 1e8), ans = 0;
while (start <= end) {
int mid = (start + end) / 2;
int cnt = 0;
int max = 0;
for (int stone : stones)
max = Math.max(max, cnt = (stone < mid ? cnt + 1 : 0));
if (max >= k) {
end = mid - 1;
} else {
ans = mid;
start = mid + 1;
}
}
return ans;
}
}
'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 순위 검색 / 2021 KAKAO BLIND RECRUITMENT - JAVA (1) | 2021.02.09 |
---|---|
[프로그래머스] 메뉴 리뉴얼 / 2021 KAKAO BLIND RECRUITMENT - JAVA (0) | 2021.02.09 |
[프로그래머스] 호텔 방 배정 / 2019 카카오 개발자 겨울 인턴십 - JAVA (0) | 2021.02.03 |
[프로그래머스] 불량 사용자 / 2019 카카오 개발자 겨울 인턴십 - JAVA (0) | 2021.02.03 |
[프로그래머스] 튜플 / 2019 카카오 개발자 겨울 인턴십 - JAVA (0) | 2021.02.03 |