[백준] 먹을 것인가 먹힐 것인가 : 7795번 - Python

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

7795번: 먹을 것인가 먹힐 것인가

 

 

 

문제의 접근 방법

 

- 이분탐색 알고리즘 활용하기

 

 

 

내가 막혔던 부분

 

- 시간 초과

 

 

 

문제 풀이 방법

 

테스트 케이스 T개 입력 받기 -> T번 만큼 반복문을 돌려 a,b(A의 수와 B의 수) 입력 받기 -> A의 크기와 B의 크기 입력 받기 -> 중첩 반복문을 통해 brute force 방법으로 A의 값들과 B의 값들의 크기 비교 -> 만약 A[i]가 B[j]보다 크면 count 하나 증가 시키기 -> 위 과정들을 반복해서 누적 합계가 저장된 count 출력!

 

 

 

다른 풀이 방법

 

이 문제는 두 리스트를 일일히 다 비교하는 방식으로 짜면 시간 초과가 나오게 된다. 따라서 '이분 탐색' 알고리즘을 써야한다. 이분 탐색을 사용해 B에서 A의 한 요소보다 작은 수들 중에 제일 큰 수의 위치(인덱스)를 찾는 것!!!

# 이분탐색 방식

T = int(input())

def binary_search(target,data):
    start = 0
    end = len(data) - 1
    res = -1
    while start <= end :
        mid = (start + end) // 2
        if data[mid] < target:
            res = mid
            start = mid + 1
        else:
            end = mid - 1
    return res

for _ in range(T):
    a,b = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    count = 0

    for i in A:
        count += binary_search(i,B) + 1

    print(count)

 

 

 

소스코드

# 전수조사 방식

T = int(input())

for _ in range(T):
    a,b = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    count = 0

    for i in range(len(A)):
        for j in range(len(B)):
            if A[i] > B[j]:
                count += 1
    print(count)