[백준/Python] 7795번 먹을 것인가 먹힐 것인가

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

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보다 큰 쌍이 몇 개나 있는지 구하는 문제이다.

이 문제는 완전탐색으로 풀게 되면 시간 초과가 나오기 때문에, 이분탐색이나 투포인터 알고리즘을 사용해서 해결해야 한다.

 

코드

for _ in range(int(input())):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    A.sort()
    B.sort()

    count = 0
    pair = 0

    for i in range(N):
        while True:
            if count == M or A[i] <= B[count]:
                pair += count
                break
            else:
                count += 1

    print(pair)

 

문제 풀이

1. 테스트 케이스의 개수를 입력받아 for문을 만든다.

2. A의 수 N, B의 수 M, A, B를 각각 입력받는다. 

3. A와 B를 sort로 오름차순으로 만든다.

4. A의 수 N범위로 for문을 돌린다. count와 M이 같은 경우(= A의 i번째 수가 B의 모든 원소보다 값이 크다)나 A의 i번째 수가 B의 count번째 수보다 작거나 같은 경우(= 오름차순으로 정렬되어있기 때문에 뒤에는 무조건 A의 i번째 수가 작기 때문에 더 이상 살펴볼 필요가 없다)에는 pair에 count를 더해주고 종료한다.

5. 마지막으로 for문을 통해 구한 pair를 출력하면 된다.