ㄷ파이썬 Python | 알고리즘 | 백준 먹을 것인가 먹힐 것인가

⭕ 파이썬 Python | 알고리즘 | 백준 먹을 것인가 먹힐 것인가

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 가장 구현하기 쉬운 방법은 A의 모든 원소와 B의 모든 원소를 비교하는 것이지만, 시간 복잡도는 O(N * M)이며, N과 M이 최대 20,000일 때는 400,000,000번의 연산이 필요하게 된다. 이는 실제 시간으로 4초 이상 걸릴 수 있어 비효율적이라고 판단하였다.
• 문제에서 주어진 조건을 고려할 때, 보다 효율적인 방법이 필요하다고 생각하였다.
  • 집합 A와 B를 오름차순으로 정렬하면, B에서 A의 원소보다 작은 원소들을 빠르게 찾을 수 있게 된다. 정렬 자체의 시간 복잡도는 O(N log⁡N) 및 O(M log⁡M)이다.
  • 정렬된 B에서 A의 원소보다 작은 원소의 개수를 찾기 위해 이진 탐색을 사용하는 것이 훨씬 빠를 것이라고 판단하였다. 이진 탐색의 시간 복잡도는 O(N log⁡M)이다.
  • 하나의 테스트 케이스에 대한 총 시간 복잡도는 O(N logN + M logM + N logM)이고, 여러 테스트 케이스가 있을 때, 총 시간 복잡도는 O( T * (N logN + M logM + N logM))이다.

 

➡️ 코드 설계하기

• 테스트 케이스 수를 입력받는다.
• 각 테스트 케이스마다 N과 M, 그리고 집합 A와 B의 원소들을 입력받는다.
• 집합 A와 B를 각각 오름차순으로 정렬한다.
• A의 각 원소에 대해, B에서 이진 탐색을 통해 A의 원소보다 작은 B의 원소의 개수를 구한다.
• Python의 bisect_left 함수를 사용하여 B에서 A의 원소보다 큰 첫 번째 원소의 인덱스를 구한다. 인덱스는 A의 원소보다 작은 B의 원소의 개수를 의미한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차 

• 시간 160ms
• bisect_left(B, a) 함수는 B 리스트에서 a보다 큰 첫 번째 원소의 인덱스를 반환한다.

import sys
import bisect

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

for _ in range(T):
    N, M = map(int, sys.stdin.readline().strip().split())
    A = list(map(int, sys.stdin.readline().strip().split()))
    B = list(map(int, sys.stdin.readline().strip().split()))

    A.sort()
    B.sort()

    count = 0

    for a in A:
        count += bisect.bisect_left(B, a)
    
    print(count)

 

 

➡️ 정답 코드

import sys
import bisect

# 테스트 케이스 수 입력받기
T = int(sys.stdin.readline().strip())

for _ in range(T):
    # N과 M 입력받기
    N, M = map(int, sys.stdin.readline().strip().split())
    
    # A와 B 입력받기
    A = list(map(int, sys.stdin.readline().strip().split()))
    B = list(map(int, sys.stdin.readline().strip().split()))

    # A와 B 오름차순 정렬
    A.sort()
    B.sort()

    # A의 각 원소에 대해 이진 탐색 수행
    count = 0
    for a in A:
        count += bisect.bisect_left(B, a)
    
    # 결과 출력
    print(count)