[백준 / python] 7759번 먹을 것인가 먹힐 것인가

오늘은 이분 탐색 유형인 백준 7759번 문제, 먹을 것인가 먹힐 것인가를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍의 개수를 구하는 것으로

A와 B의 각 원소로 만들 수 있는 모든 쌍을 계산하는 것은 시간복잡도가 높아지므로 비효율적입니다.

따라서, 이를 개선하기 위해 이분 탐색을 활용하여 효율적으로 해결할 수 있습니다!

 

A의 각 원소에 대해 B에서 그보다 작은 값들의 개수를 찾아야 하므로

먼저, B를 정렬하고 A의 특정 원소보다 작은 B의 원소 개수를

이분 탐색(bisect_left)을 통해 빠르게 찾는 방법으로 코드를 구현해야 합니다!

 

✔️ 가능한 시간복잡도

A, B 모두 크기가 최대 20,000이므로, 모든 쌍을 비교하면 시간복잡도 O(N×M)로 계산되어

최악의 경우 O(400,000,000)에 이르러 매우 많은 연산이 필요합니다.

 

하지만, 이분 탐색 알고리즘을 활용한다면 B를 정렬하는데 O(MlogM), 

A의 각 원소에 대해 이분 탐색을 수행하는데 O(NlogM) 시간이 걸리므로

전체 시간복잡도는 O(MlogM + NlogM)으로 계산됩니다!

 

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 먼저 테스트 케이스의 수 T를 입력받습니다.

2. 각 테스트 케이스에 대해 A와 B의 크기와 원소를 입력받습니다.

3. 이분 탐색을 수행하기 위해 배열B를 정렬합니다.

4. A 배열의 각 원소에 대해 B 배열에서 bisect_left를 사용하여 조건에 맞는 쌍을 찾습니다.

5. 각 테스트 케이스에 대해 계산된 쌍의 개수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

---

📌 정답 코드

import sys, bisect

# 입력 받기
T = int(sys.stdin.readline())

for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    arr_A = list(map(int, sys.stdin.readline().split()))
    arr_B = list(map(int, sys.stdin.readline().split()))
    arr_B.sort() # 배열B 정렬

    count = 0

    # A의 각 원소에 대해 B에서 더 작은 원소의 개수를 이분 탐색으로 계산
    for i in arr_A:
        check = bisect.bisect_right(arr_B, i - 1)
        count += check

    print(count)

이분 탐색 알고리즘을 활용하여 시간복잡도를 줄이고 더 빠른 연산이 가능했습니다!

파이썬의 내장함수인 bisect에 적응할 수 있는 시간이었습니다 ㅎㅎ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no