백준 - 7795번 먹을 것인가 먹힐 것인가 python 문제풀이 [Hellfer]

🔷 알고리즘 분류 - 정렬, 두 포인터,  난이도 - 실버 3

 

문제

 

심해에는 두 종류의 생명체 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보다 큰 쌍의 개수를 출력한다.

 

 

---

 

이분탐색이란?

 

- 정렬된 배열에서 목표 값을 찾거나 특정 조건을 만족하는 값을 빠르게 찾기 위해 사용하는 알고리즘입니다.

시간 복잡도는 O(log n)으로 매우 효율적이며 정렬이 되어있을 경우에만 사용가능합니다.

 

기본 원리

 

1. 배열의 시작 인덱스(left)와 끝 인덱스(right)를 설정

2. mid = (left+right)//2로 중간값을 계산

 

3.

- 중간 값이 목표 값과 일치하면 탐색을 종료하고 출력합니다.

- 중간 값이 목표 값보다 작다면 (left=mid+1)

- 중간 값이 목표 값보다 크다면(right=mid-1)

 

4. left가 right보다 커질 때까지 위 과정을 반복합니다.

 

---

🔶문제 풀이 -  두 포인터를 이용한 풀이

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    a = sorted(map(int, input().split()))
    b = sorted(map(int, input().split()))
    
    start=0 # b 리스트 시작 인덱스
    count=0 # a가 b보다 크면 1씩 증가
    
    for j in range(n): # a배열의 크기만큼 반복
        while True:
        # start가 b리스트 끝에 도달했거나 b인덱스의 크기가 a인덱스 보다 크다면
            if start==m or a[j]<=b[start]:
                count+=start # 현재 start값을 count에 더해줌(a보다 작은 b의 개수)
                break
            else:   
                start+=1 # a가 b보다 클 경우
                
    print(count)