이분 탐색을 이용하는 방법이기 때문에 다음을 모두 정해야 한다.

1. 가능한 정답의 최솟값(left)
2. 가능한 정답의 최댓값(right)
3. 정답을 하나 결정했을 때, 이것이 문제의 조건에 맞는지 검사하는 방법(go 함수)
4. 조건에 맞는 경우 정답을 더 크게 해야 하는지 작게 해야 하는지 결정

백준 1790번 수 이어 쓰기 2

문제

나의 풀이

import java.util.*;

public class Main {
    static long calc(int n) { // 수의 길이 구하기
        long answer = 0;
        for(int start = 1, len = 1; start <= n; start *= 10, len++) {
            int end = start * 10 - 1; // 그 자릿수 중 가장 마지막 값
            if(end > n) { 
                end = n;
            }
            answer += (long) (end - start + 1) * len;
        }
        return answer;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        if(calc(n) < k) { // n 까지의 길이가 k 보다 작은 경우(불가능함)
            System.out.println(-1);
            System.exit(0);
        }
        
        int left = 1;
        int right = n;
        int answer = 0;
        while(left <= right) {
            int mid = (left + right) / 2;
            long len = calc(mid);
            if(len < k) {
                left = mid + 1;
            } else {
                answer = mid;
                right = mid - 1;
            }
        }
        
        String s = Integer.toString(answer);
        long l = calc(answer);
        System.out.println(s.charAt(s.length() - 1 - (int)(l - k)));
    }
}

N번째 수의 길이는 자리수 별로 길이를 계산하는 방식으로 알 수 있다.
이 점을 이용해서 이분 탐색으로 N을 결정하고 그 때 마다 수의 길이를 재보고 K보다 작거나 같은지 비교해본다. 처음에 left는 1, right는 N으로 두고 이분탐색을 하면 된다.

결과

백준 1654번 랜선 자르기

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean check(long[] a, int m, long x) {
        int count = 0;
        for(int i = 0; i < a.length; i++) {
            count += a[i] / x;
        }
        return count >= m;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long a[] = new long[n];
        long max = 0;
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            max = Math.max(max, a[i]);
        }
        
        long left = 1;
        long right = max; // 입력 받은 랜선 길이 중 최댓값
        long answer = 0;
        while(left <= right) {
            long mid = (left + right) / 2;
            if(check(a, m, mid)) { // mid로 m개의 랜선을 만들 수 있는 경우
                answer = Math.max(answer, mid); // 최대 길이 구하기
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(answer);
    }
}

길이 x로 잘랐을 때 n개 이상 만들 수 있으면 x를 크게 만들고 n개 이상을 만들 수 없다면 x를 작게 만드는 방식으로 진행한다. 처음에 left는 1, right는 입력 받은 랜선 길이 중 최댓값으로 둔다.
check 함수는 길이 x로 자르면 m개의 랜선을 만들 수 있는지 여부를 리턴하는 함수다.

결과

백준 2805번 나무 자르기

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean check(long[] a, long mid, long m) {
        long sum = 0;
        for(int i = 0; i < a.length; i++) {
            if(a[i] - mid > 0) {
                sum += a[i] - mid;
            }
        }
        return sum >= m;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        long a[] = new long[n];
        long left = 0;
        long right = 0;
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            right = Math.max(right, a[i]); // 나무들 중 최대 높이를 right로
        } 
        
        long answer = 0;
        while(left <= right) {
            long mid = (left + right) / 2;
            if(check(a, mid, m)) { // 길이 m을 만들 수 있는 경우
                answer = Math.max(answer, mid); // 절단기의 최대 높이 구하기
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(answer);
    }
}

절단기의 높이를 높일수록 가져갈 수 있는 나무의 길이는 더 작아진다.
절단기의 높이를 낮출수록 가져갈 수 있는 나무의 길이는 더 커진다.
처음에 left는 0, right은 가장 높은 나무의 높이로 둔다.
그런 다음 x라는 높이로 잘라보고 나온 길이의 합을 c라하면 c가 m보다 크거나 같으면 x를 크게, 아니면 x를 작게 만든다.

결과

인프런 한 번만 사용한 최초 문자

문제

나의 풀이

public class FirstChar {
    public static int solution(String s) {
        HashMap<Character, Integer> sh = new HashMap<>();
        for(char x : s.toCharArray()) {
            sh.put(x, sh.getOrDefault(x, 0) + 1);
        }
        for(int i = 0; i < s.length(); i++) {
            if(sh.get(s.charAt(i)) == 1) {
                return i + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(FirstChar.solution("statitsics"));
        System.out.println(FirstChar.solution("aabb"));
    }
}

결과