징검다리 건너기
Last update: a year ago by nowwaterReading time: 2 min
문제
코드
코드 보기
import java.util.Scanner;public class intern20195 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int k = sc.nextInt(), stones[] = new int[10];for (int i = 0; i < 10; i++) {stones[i] = sc.nextInt();}Solution sol = new Solution();System.out.println(sol.solution(stones, k));}}class Solution {static int[] stones;static int k;public int solution(int[] mstones, int mk) {stones = mstones; k = mk;int left = 1, right = 200000000;while(left < right){int mid = (left + right) / 2;if(checkCondition(mid)) right = mid;else left = mid + 1;}return left;}private boolean checkCondition(int m) {for (int i = 0; i < stones.length; i++) {if(stones[i] - m <= 0){if(i + k - 1 >= stones.length) break;boolean flag = true;for (int j = i + 1; j < i + k; j++) {if(stones[j] - m > 0) {flag = false;i = j;break;}}if(flag) return true;}}return false;}}
⭐️느낀점⭐️
카카오 기출 문제와 백준 기출 문제는 느낌이 다르다는 것을 알았다.
다양한 알고리즘 유형이 나오지만 또 풀이방법이 어려운 건 아닌 깔끔하고 진짜 다양한 문제의 요구 사항을 맞추는 문제인 듯 하다.
풀이 📣
1️⃣ 최대한으로 징검다리를 건널 수 있는 인원을 구하기 위해 이분탐색을 실시한다.
- 각 돌다리의 수명이 2억 이하인 자연수이므로, 최대로 건너갈 수 있는 인원 m 도 2억명이다.
2️⃣ 현재 최대 인원이 돌다리를 지날 수 있는지 확인한다.
- 연속으로 k 개의 돌다리가 수명을 다했다면 다음 차례의 사람은 건너갈 수 없다.- 한 명이 지나갈 때 마다 각 돌다리의 수명이 1씩 깎이므로, 연속된 k 개의 돌다리가 (수명 - m) <= 0 이라면 m 명보다 더 건널 수 없다.
3️⃣ 현재 인원mid보다 더 클 수 없다면 최대치 right 를 mid 값으로 변경해주고, mid 보다 많은 인원이 가능하다면 최소 인원left 에 mid + 1 로 변경해준다.
4️⃣ 최종적으로 구한 최대 가능 인원을 출력한다.
실수 😅
돌다리의 수명이 2억이하이므로 모든 칸을 탐색하면서 1씩 줄이는 것은 불가능할 것이라 생각했다.
나름대로 연산을 줄여보려고 우선순위 큐를 만들어서 한 번에 같은 수명을 가진 돌다리를 모두 지우고 사용 불가능함을
boolean타입으로 표시해서 풀려고했다.그리고 연속되는 K 개의 돌다리가 수명을 다했는지 확인하는 식으로 했었다.
하지만 이 방법은 인원수를 m이라고 하고 돌다리의 개수를 n 이라고 하였을 때
m*n^2*logn이라는 어마어마한 시간이 걸린다따라서 다른 방법을 찾아보고 이분 탐색을 통해
nlogm시간에 동작하는 풀이를 찾을 수 있었다.