이분 탐색과 완전 탐색
프로그래머스 2019 카카오 인턴십 Level 3 징검다리 건너기를 Java로 풀어보았다. 처음에는 완전 탐색으로, 그 다음에는 조금 변형된 완전 탐색으로 최소한의 연산 횟수를 줄였다고 생각했는데 테스트 케이스 7~13번은 끝까지 통과가 되지 않았다. 다른 케이스들은 실행 시간이 확실히 줄어든 게 보이는데 저 케이스들은 도저히 통과가 안 되는 것을 보니 다른 탐색법을 써야하는구나를 늦게 깨달았다.
문제 링크를 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/64062
변형된 완전탐색
처음에는 0번 인덱스부터 시작해서 k개 만큼을 한 묶음으로 탐색하며 각 묶음의 최댓값 중 최솟값을 찾는 방식으로 풀었다.
이때 모든 묶음을 다 탐색할 것은 아니고, 만약 현재 탐색 중인 묶음에서 현재까지 나온 최댓값 중 최솟값보다 더 크거나 같은 값을 발견하게 되면 그 값이 포함된 묶음들은 볼 필요가 없다.
그래서 바깥 for문에 label 을 붙여 건너 뛰게 만들었다.
int solution(int[] stones, int k) {
int answer = Integer.MAX_VALUE;
L1:
for(int i=0; i<stones.length-k+1; i++){
int max = -1;
for(int j=i; j<i+k; j++){
if(answer<=stones[j]) {
i = j; // 현재까지 나온 최댓값 중 최솟값 이상의 값이 존재할 묶음들은 다 패스
continue L1;
}
if(max<stones[j]) max = stones[j];
}
if(answer>max) answer = max;
}
return answer;
}하지만 이렇게 불필요한 확인을 다 건너뛰게 하더라도 테스트 케이스 7~13은 여전히 통과하지 못했다.
이분 탐색
이분 탐색과 for each문을 사용해서 해결했다. 사실 내가 직접 생각해낸 것은 아니고, 결국 다른 사람의 풀이를 참고했다. 화가 난다..!!
이분 탐색은 내가 많이 사용해 본 탐색 기법이 아니라서 이분 탐색으로 풀어야하는 문제를 마주쳐도 여기에 이분 탐색을 적용해야겠다는 생각 자체를 떠올리지 못하는 게 가장 큰 문제다.
특정 문제를 마주했을 때 이 문제에 가장 적합한 풀이는 과연 무엇일지 떠올릴 수 있는 힘 자체가 없다...
어쨌든 이분 탐색으로 억덕해 푸냐면.. 건널 수 있는 사람 수를 타겟으로 삼아 이분 탐색을 진행하는 것이다.
아래는 이분 탐색으로 해결한 solution 코드다.
int solution(int[] stones, int k) {
int answer = 0;
int min = 1; int max = 200000000;
while(min<=max){
int mid = (min+max)/2;
if(isCrossable(stones, k, mid)){ // mid 인원으로 넘을 수 있으면
min = mid+1; // 좌측 지표를 중간 쪽으로 옮기자
answer = Math.max(answer, mid);
}
else{ // mid 인원으로 못 건너면 우측 지표를 중간 쪽으로 옮기자
max = mid-1;
}
}
return answer;
}mid 만큼의 인원으로 건널 수 있는지 없는지에 따라서 양쪽 지표를 움직이면서 양쪽 지표가 역전되는 순간 탐색을 마무리하면 된다.
그렇다면 mid 만큼의 인원으로 건널 수 있는지 없는지는 억덕해 판단할까? 다음 isCrossable 메소드를 통해 알아낼 수 있다.
Boolean isCrossable(int[] stones, int k, int mid){
int howFarAtOnce = 0;
for(int num: stones){
if(num - mid < 0) howFarAtOnce++; // 밟을 수 없는 칸이 몇 개나 연속되는지
else howFarAtOnce = 0;
if(howFarAtOnce==k) return false; // 만약 한 번에 건너야 하는 칸 수가 k개를 때리면 못 건너는 것
}
return true;
}for each문을 사용해서 효율성을 높여주자.
아래는 위의 코드들을 다 합한 내가 제출한 코드다.
import java.io.*;
public class Bridge {
static int solution(int[] stones, int k) {
int answer = 0;
int min = 1; int max = 200000000;
while(min<=max){
int mid = (min+max)/2;
if(isCrossable(stones, k, mid)){
min = mid+1;
answer = Math.max(answer, mid);
}
else{
max = mid-1;
}
}
return answer;
}
static Boolean isCrossable(int[] stones, int k, int mid){
int howFarAtOnce = 0;
for(int num: stones){
if(num - mid < 0) howFarAtOnce++;
else howFarAtOnce = 0;
if(howFarAtOnce==k) return false;
}
return true;
}
public static void main(String args[]) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
int k = 3;
bfw.write(String.valueOf(solution(stones, k)));
bfw.close();
}
}오늘 배운 것
- 현재 풀이에서 더 개선시킬 수 없는 것 같으면 새로운 풀이를 고민해보자.
- 다양한 탐색법에 대해 머릿속에 저장해두자... 오늘은 이분 탐색을 머릿속에 집어 넣어보자
