알고리즘/baekjoon

[ baekjoon ] 먹을 것인가 먹힐 것인가 7795번 ( python )

Yanoo 2021. 8. 7. 23:03
728x90
반응형

문제

백준 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를 먹을

www.acmicpc.net

 

풀이

처음에는 아래 코드처럼 큰 걸 발견했을 때 cnt를 증가시키도록 했지만 시간초과가 떴다.

import sys

input = sys.stdin.readline

t = int(input())

while t:

    cnt = 0

    n, m = map(int, input().split())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    for i in A:
        for j in B:
            if i > j:
                cnt+=1
    
    print(cnt)

    t-=1

 

그래서 정렬을 한 후 이분탐색으로 풀었다.

import sys
import bisect

input = sys.stdin.readline

t = int(input())

while t:

    cnt = 0

    n, m = map(int, input().split())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    A.sort()
    B.sort()

    for i in A:
        cnt += bisect.bisect_left(B, i)
    
    print(cnt)
    t-=1
728x90
반응형