[BOJ - Silver III] 먹을 것인가 먹힐 것인가 / ⭕

먹을 것인가 먹힐 것인가

1. 제출 코드 (42분 20초 / 이분 탐색)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int T = Integer.parseInt(br.readLine());

        for(int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int[] aGroup = new int[a];
            int[] bGroup = new int[b];

            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < a; i++) {
                aGroup[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < b; i++) {
                bGroup[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(bGroup);
            int answer = 0;
            for(int i = 0; i < a; i++) {
                answer += binary_search(aGroup[i], bGroup);
            }
            System.out.println(answer);
        }
    }

    public static int binary_search(int value, int[] group) {
        int start = 0;
        int end = group.length - 1;
        int mid = 0;

        while(start <= end) {
            mid = (start + end) / 2;
            if(value > group[mid]) start = mid + 1;
            else end = mid - 1;
        }
        return start;
    }
}

 

2. 구현 로직

B 그룹의 원소들 중 A 그룹의 원소보다 작은 개수를 구하면 되는 문제이다. 일단 B그룹을 정렬하고 A 원소보다 작은 원소 중 가장 근접한 원소의 위치를 찾으면 그 기준으로 왼쪽은 다 작은 원소이다.

1. A그룹은 비교 대상이 아니기 때문에 B 그룹만 정렬
2. 이분 탐색 함수를 만들어서 start의 위치를 찾는다.
3. start를 기준으로 왼쪽은 전부 value보다 작은 값이므로 start를 return 배열이므로 - 1이 기본적으로 되어 있기 때문에 그대로 반환
4. 각 원소마다 적용하여 정답 추출

3. 유의할 점

• N과 M이 20,000이므로 시간복잡도가 O(N^2)이면 시간 초과가 날 것 같으니 주의해야 한다.