[BOJ][Python] 7795번 - 먹을 것인가 먹힐 것인가[정렬- 실버 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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

 

예제 입력 

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

예제 출력 

7
1

문제의 핵심은 A 리스트의 요소들이 B 리스트 요소들을 몇개나 포함할 수 있는가 혹은 A 요소보다 작은 B 요소들의 조합을 몇개나 만들수 있는가이다.

 

이 아이디어를 토대로 정리하자면 A 리스트의 요소가 B 리스트 요소 내부 어디에 위치하는지를 알게되면, 자연스럽게

A 리스트 요소보다 작은 B 요소들의 갯수를 알 수 있게된다.

 

이를 위해 이분탐색을 진행했다. 완전탐색을 진행하게 되면 2중 for문을 사용하게 되므로, 시간초과가 나게된다.

import sys
import bisect

T = int(sys.stdin.readline())
for _ in range(T):
  AB_Numbers = list(map(int, sys.stdin.readline().split()))
  A = list(map(int, sys.stdin.readline().split()))
  B = list(map(int, sys.stdin.readline().split()))
  sorted_A = sorted(A)
  sorted_B = sorted(B)
  count = 0
  for a in sorted_A:
    # 정렬된 A의 값이 [1,1,3,7,8]
    # 정렬된 B의 값이 [1,3,6]
    # 위와 같이 A,B가 정렬된다. 문제의 핵심은 A의 요소들이 B 리스트 내부에서
    # 어디에 위치할 수 있는가를 기준으로 누적을 해주면된다.
    """
    만약 값이 a의 요소가 1일 경우 B 리스트에서 가장 첫번째에 들어가게 되므로 index의 값은 0을
    반환하게 된다. 
    반면 a의 요소가 8일 경우 B 리스트에서 3번째 포지션을 반환!
    이렇게 되면 자연스럽게 내가 원하는 요소보다 작은 B의 요소들의 숫자를 알게되므로
    누계를 해주면 정답이 된다.
    """
    
    # sorted_B에 정렬되어 삽입될 수 있는 포지션을 반환 
    count+=bisect.bisect_left(sorted_B, a)
  print(count)