백준 7795번 - 먹을 것인가 먹힐 것인가 - 파이썬(Python)

문제 링크

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

문제

 

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력 조건

• 각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

 

입력 예시

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

출력 예시

7
1

풀이 전 생각

 그냥 일일히 비교해서 count를 해주면 되지 않을까? 하고 생각했지만, 시간 초과가 발생했다.

 

예제 코드1(시간 초과)

t=int(input())
for i in range(t):
    count=0
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i]>b[j]:
                count+=1
    print(count)

시간 초과가 발생하고 다시 문제의 조건을 살펴보니 N,M의 범위가 20000까지였고 위의 코드처럼 해결하려면 O(NM) 즉, 4억번의 연산을 필요로 하기때문에  1초의 시간제한에 걸렸다. 그리고나서 백준의 알고리즘 분류를 보고 이분 탐색을 사용하면 O(NlogM)으로 충분히 통과할 것이라 생각하고 코드를 수정했다. 

예제코드2(성공)

t = int(input())
for _ in range(t):
    count = 0
    n, m = map(int, input().split())
    a = list(map(int, input().split())) 
    b = list(map(int, input().split()))
    b.sort() 
    
    for num in a:
        left, right = 0, len(b) - 1
        while left <= right:
            mid = (left + right) // 2
            if b[mid] < num:
                left = mid + 1
            else:
                right = mid - 1
        count += left 
    print(count)

찾아보니 bisect라는 라이브러리를 사용하면 손쉽게 이분 탐색을 할 수 있지만, 코드를 작성하는 데 능숙해질 필요가 있을 것 같아 직접 구현해서 사용했다.

생각

 전에는 시간 초과가 발생하면 원인을 찾지 못했는데, 최근에 문제를 풀고나서 시간초과를 자주 보면서 시간 복잡도에 관해 생각할 기회가 많았다. 이제는 문제를 보고 '이 풀이를 선택하면 시간 초과가 발생하겠구나' 하고 어느정도 감이 잡히는 것 같다.