[백준] 7795 - 먹을 것인가 먹힐 것인가

문제 링크

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

느낀 점

A -> B 집합이라고 했을 때, 경우의 수가 B의 원소의 갯수 ** A의 원소의 갯수가 나오기 때문에 시간 초과가 발생한다.(1 ≤ N, M ≤ 20,000)

따라서 A 집합의 원소가 B 집합의 어느 분위수에 해당하는지를 계산하고 그 인덱스를 더해주는 방식으로 구해야 O(NlogN)이 되어서 시간초과가 발생하지 않을 수 있다. 문제를 보면 이것을 생각하기 힘들어서 고생했는데, 분위수, 순서를 구하는데 시간 초과를 피해야한다면 이분탐색으로 접근하면 될 것 같다는 느낌이 들었다. 

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    N_list = sorted(list(map(int, sys.stdin.readline().split())))
    M_list = sorted(list(map(int, sys.stdin.readline().split())))
    count = 0
    for comp in N_list:
        s, e = 0, len(M_list) - 1
        res = -1
        while s <= e:
            m = (s + e) // 2
            if M_list[m] < comp:
                res = m
                s = m + 1
            else:
                e = m - 1
        count += res + 1
    print(count)