https://www.acmicpc.net/problem/17266

백준 실버4 17266 어두운 굴다리

쉽게 풀릴리가 없는 코딩테스트...
그냥 머릿속에서 생각나는대로 써서 금방 풀었다.
(문제 이해 포함 한 5~10분?)

시도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());
        int M = Integer.parseInt(bufferedReader.readLine());
        int arr[] = new int[N+1];
        int len = 0;

        String str = bufferedReader.readLine();
        for(int i=0;i<M;i++){
            len = Integer.parseInt(str.split(" ")[i]);
            arr[len] = 1;
        }

        int count = 0, max = 0;
        for(int i=0;i<=N;i++){
            if(arr[i] == 1){
                max = Math.max(count, max);
                count = 0;
            } else{
                count++;
            }
        }
        max = Math.max(count, max);

        System.out.println(max);
    }
}

시간초과...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());
        int M = Integer.parseInt(bufferedReader.readLine());
        int arr[] = new int[N+1];
        int len = 0;
        int distance = 0, max_d = 0;
        String str = bufferedReader.readLine();

        for(int i=0;i<M;i++){
            len = Integer.parseInt(str.split(" ")[i]);
            arr[i] = len;
        }

        for(int i=1;i<M;i++){
            distance = Math.abs(arr[i-1] - arr[i]);
            max_d = Math.max(distance, max_d); //가로등 사이 거리 가장 큰 값
        }

        max_d = Math.max(max_d, arr[0]); //처음 가로등~시작점
        max_d = Math.max(max_d, N-arr[M-1]); //마지막 가로등~끝

        System.out.println(max_d);
    }
}

시간초과...

풀이

그래서 문제 유형을 봤더니 이분탐색?
이걸 이분탐색으로 풀다니... 게다가 이게 전형적인 문제라니...
이분탐색 문제 많이 풀어봐야겠다. 감이 안 온다.
대체 왜 이분탐색을 사용하는지 모르겠어서 이해하는데도 꽤 오래 걸렸다.

이분탐색을 쓰는 이유는 굴다리의 길이 N이 10만, 가로등의 개수도 10만까지 있어 매우 길다.
내가 푼 코드로 풀면 10만번 이상 탐색해야 하는 것.
그래서 가로등의 높이가 임의로 H라면 다 비출 수 있는지 판단해가며 다 비출 수 있다면 H의 범위를 /2로 확 줄여 탐색 횟수를 낮추는 것이다.

사실 알고보니 이렇게 쓴다를 알았던거지 아무것도 모르는 상태에서 풀라고 하면 잘 모를 것 같다 ㅠㅠ
그냥 시간 줄이는 방법 이라고 생각하고 항상 염두에 두고 있어야 할 듯 ㅠ_ㅠ

추가로 이분탐색으로 하고 split으로 입력 값 나눴는데 그것도 시간초과가 걸렸다.
아무래도 입력 자체가 많을 수 있어서 그런 듯 싶다.
앞으로는 그냥 맘 편하게 StringTokenizer 써야지

최종

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());
        int M = Integer.parseInt(bufferedReader.readLine());
        int arr[] = new int[M];

        int len = 0;
        int max = 0;
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int i=0;i<M;i++){
            len = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = len;
        }

        int start = 1, end = N;
        // 이분 탐색
        while(start <= end){
            int point = 0;
            int mid = (start + end) / 2;
            boolean flag = true;

            for(int i=0;i<M;i++){
                if(arr[i] - mid <= point){
                    point = arr[i] + mid;
                } else{
                    flag = false;
                    break;
                }
            }

            if(N - point > 0)
                flag = false;
            else
                flag = true;

            if(flag){ //모두 비추기 가능
                max = mid;
                end = mid - 1;
            } else{
                start = mid + 1;
            }
        }

        System.out.println(max);
    }
}