[python/백준] 7795. 먹을 것인가 먹힐 것인가(S3)

📌 문제 탐색하기

👉 문제바로가기

T: 테스트 케이스의 갯수
N, M: 각각 A의 수와 B의 수를 의미 (1 ≤ N, M ≤ 20,000)

각 테스트케이스 마다 A를 리스트에 저장하고, B를 리스트에 저장합니다. i, j가 각각 A리스트와 B리스트의 인덱스라고 할 때 우리가 구해야 하는 것은 A[i] > B[j]를 만족하는 i, j쌍의 갯수입니다.

📌 알고리즘 선택

처음 문제를 보면 단순히 A와 B의 요소를 모두 탐색하여 비교하는 방법을 생각할 수 있으나 코딩 문제풀이에서는 시간복잡도를 고려해보아야 합니다. 모든 요소를 탐색할 경우 i, j에 대한 이중 for문을 사용할 수 있는데 이때 최악의 경우 (20,000)^2 = 400,000,000번의 연산이 수행되며 이는 1초동안 수행될 수 없는 연산 횟수입니다. 따라서 미리 정렬시킨 후 A의 원소보다 B의 원소가 크면 해당되는 B의 원소보다 더 큰 인덱스를 가진 원소는 비교할 필요가 없는것이죠. 이렇게 필요하지 않은 반복을 줄이면 되겠습니다.

N, M의 크기가 작지 않기 때문에 이진 탐색을 생각해볼 수 있습니다. 이진 탐색으로 각 리스트의 원소를 비교한 후 비교를 하지 않아도 되는 원소를 굳이 반복해서 탐색하지 않는 경우 효율적이겠네요.

가능한 시간복잡도

A리스트 각각의 요소들에 대해 B리스트 요소를 이진 탐색하면 시간복잡도는 O(logM)입니다. 여기서 A원소 는 총 N개이므로 총 시간복잡도는 O(NlogM)이 되겠네요. 따라서 약 180,000회의 연산이 필요할 것이고 이는 1초안에 충분히 가능한 연산 횟수입니다.

📌 코드 설계하기

1. 테스트 케이스의 개수(T)를 Input받은 후 해당 테스트 케이스 수만큼 A의 수(N), B의 수(M), A리스트, B리스트를 Input받습니다.
2. A, B리스트를 정렬합니다.
3. A리스트의 각 원소에 대해 B의 리스트 원소를 이진 탐색하며 크기를 비교하고, A리스트 원소가 B리스트 원소보다 큰 경우는 count를 1씩 증가시킵니다.
4. 각 케이스마다 count를 출력합니다.

📌 정답 코드

import sys

T = int(sys.stdin.readline())

def search(array, target, start, end):
    result = -1
    while start <= end:
        mid = (start + end) // 2
        if array[mid] < target:
            result = mid
            start = mid + 1
        else:
            end = mid - 1 
    return result

for _ in range(T):
    A, B = map(int, sys.stdin.readline().split())
    arrA = list(map(int, sys.stdin.readline().split()))
    arrB = list(map(int, sys.stdin.readline().split()))
    
    arrA.sort()
    arrB.sort()

    count = 0

    for i in range(A):
        count += (search(arrB, arrA[i], 0, B-1)+1)

    print(count)

📌 다른 풀이

bisect라이브러리를 활용하면 더 간단하게 해결할 수 있습니다.

import sys
import bisect

T = int(sys.stdin.readline())

for _ in range(T):
    A, B = map(int, sys.stdin.readline().split())
    arrA = list(map(int, sys.stdin.readline().split()))
    arrB = list(map(int, sys.stdin.readline().split()))
    
    arrA.sort()
    arrB.sort()

    count = 0

    for i in range(A):
        count += bisect.bisect(arrB, arrA[i]-1)

    print(count)

bisect라이브러리

• https://docs.python.org/ko/3.7/library/bisect.html