글 읽기 - 이분탐색을 통해서 해결해보려고 하는데 접근이 막힙니다.

imonlyone 1년 전 0

이분 탐색을 통해서 해결하는 것 까진 추론되었습니다.

그치만 왜 중복 된 요소를 제거하는지 이해가 잘 가지 않습니다.

에러가 나오는 부분은 31번 logic 메소드 입니다. 중복을 제거하였어서 첫 번째 예제로 실행 할 경우

당연히 에러가 나옵니다. 이 문제의 접근 방법을 알 수 있을까요?

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

class Main {
    static StringBuilder sb;
    static StringTokenizer st;
    static BufferedReader br;
    static int N;
    static int[] origin, distinct;

    public static void main(String[] args) throws IOException {
        input();
        logic();
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        origin = new int[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            origin[i] = num;
        }

        distinct = Arrays.stream(origin).distinct().toArray();
    }
    
    // ArrayIndexOutOfBounds
    static void logic() {
        Arrays.sort(origin);
        for (int i = 0; i < N; i++) {
            System.out.print(lowerBound(origin, 0, N, distinct[i]) + " ");
        }
    }

    static int lowerBound(int[] arr, int L, int R, int X) {
        while (L < R) {
            int mid = (L + R) / 2;
            if (arr[mid] >= X) R = mid;
            else L = mid + 1;
        }
        return L;
    }

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이분탐색을 통해서 해결해보려고 하는데 접근이 막힙니다.

imonlyone 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말