백준 17393번
https://www.acmicpc.net/problem/17393

문제

---

생각하기

---

• 이분 탐색 알고리즘 문제이다.

  • 점도 지수는 정렬이 이미 되어있다.
  • 잉크 지수 배열에서 점도 지수 배열의 값 중에 자신보다 작거나 같은 친구를 선택하는데, 같을 경우 가장 뒤에 있는 친구를 선택한다.

• 배열의 index를 이분 탐색을 통해서 찾아야 한다.
  • 이분 탐색을 통해서 얻어진 mid 값 index를 현재 출발한 출발한 low값과 빼서 총 몇 개의 칸을 칠할 수 있는지를 정답으로 구하면 된다.

동작

코드

---

Java

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static long N; // 통로의 길이
    private static final int MAX = 500000;
    private static long[] arrA = new long[MAX]; // 잉크 지수
    private static long[] arrB = new long[MAX]; // 점도 지수

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Long.parseLong(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arrA[i] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arrB[i] = Long.parseLong(st.nextToken());
        }

        // 내가 있는 칸을 포함하되 index는 0이 된다.
        // index를 이분 탐색을 통해서 찾아야됨
        for (int i = 0; i < N; i++) {
            // 여기 인덱스를 기준으로 i부터 idx까지 몇개를 칠 할 수 있는지 적어야됨
            sb.append(binarySearch(i, N - 1, arrA[i]) - i).append(' ');
        }


        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static long binarySearch(long low, long high, long inkValue) {
        if (low > high) {
            return -1;
        }

        // 같은 값 중에서 가장 뒤의 값을 선택해야 됨.
        long mid = (low + high) / 2;
        // res가 true이면 더 mid를 더 올려도됨
        if (check(mid, inkValue)) {
            long ret = binarySearch(mid + 1, high, inkValue);
            if (ret == -1) {
                return mid;
            } else {
                return ret;
            }
        } else {
            return binarySearch(low, mid - 1, inkValue);
        }
    } // End of binarySearch

    private static boolean check(long mid, long inkValue) {
        // 잉크지수 보다 점도지수가 작거나 같은지 확인해야됨
        if (arrB[(int) mid] <= inkValue) {
            return true;
        }
        return false;
    } // End of check
} // End of Main class

Kotlin

import java.io.*
import java.util.*

private var N: Long = 0
private const val MAX = 500_000;
private val inkArr = LongArray(MAX)
private val viscoArr = LongArray(MAX)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    N = br.readLine().toLong()

    var st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        inkArr[i.toInt()] = st.nextToken().toLong()
    }

    st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        viscoArr[i.toInt()] = st.nextToken().toLong()
    }

    for (i in 0 until N) {
        sb.append(binarySearch(i, N - 1, inkArr[i.toInt()]) - i).append(' ')
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun binarySearch(low: Long, high: Long, inkValue: Long): Long {
    if (low > high) {
        return -1;
    }

    val mid = (low + high) / 2;
    if (check(mid, inkValue)) {
        val ret = binarySearch(mid + 1, high, inkValue)
        if (ret == -1L) {
            return mid;
        } else {
            return ret;
        }
    } else {
        return binarySearch(low, mid - 1, inkValue);
    }
} // End of binarySearch

private fun check(mid: Long, inkValue: Long): Boolean {
    if (viscoArr[mid.toInt()] <= inkValue) {
        return true
    }
    return false
} // End of check