Post

먹을 것인가 먹힐 것인가 백준 7795번 정렬

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

문제

심해에는 두 종류의 생명체 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.

diagram

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

원래라면 이 문제를 이진탐색으로 풀어야하지만 정렬로도 풀수 있다고 합니다.

그래서 시도 해봤는데 시간초과 아마 파이썬이라서 그런거 같습니다. 이진 탐색은 나중에 다룰 것이니 지금은 정렬로 푸는 것만 올리고 넘어갈려고 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
input=sys.stdin.readline

def func(a_case,b_case):
    a_case.sort(reverse=True)
    b_case.sort(reverse=True)
    total = 0
    minum = False
    for i in range(n):
        count = 0
        for j in range(m):
            if a_case[i]<b_case[-1]:
                minum=True
                break
            if a_case[i]>b_case[j]:
                count+=1
            else:
                continue
        total += count
        if minum:
            break
    return total
    
loop = int(input())
for i in range(loop):
    n,m = map(int,input().split())
    a_case = list(map(int,input().split()))
    b_case = list(map(int,input().split()))
    print(func(a_case,b_case))

정렬을하고 하나씩 비교를 합니다. 그런데 특정 조건에서는 비교를 하지 않고 바로 빠져나오게 해봤지만 여전히 시간초과가 나오네요

This post is licensed under CC BY 4.0 by the author.