[백준] 7795번 : 먹을 것인가 먹힐 것인가 (Python / 파이썬)

문제

심해에는 두 종류의 생명체 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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

 

 

조건 및 입출력

1. 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

2. 각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

3. 시간 제한 : 1초 

4. 메모리 제한 : 256MB

 

 

코드 (PyPy3)

# 정의부
import sys

# 입력부
test=int(sys.stdin.readline());
result=0;

# 처리부
for i in range(test):
    a_count,b_count=map(int,sys.stdin.readline().split());

    a=sorted(list(map(int,sys.stdin.readline().split())));
    b=sorted(list(map(int,sys.stdin.readline().split())));

    for j in a:
        for k in b:
            if(j>k):
                result+=1;
            else:
                break;
# 출력부
    print(result);
    result=0;

 

 

풀이 과정

sys.stdin.readline()으로 값을 읽어오지 않으면 시간 초과가 된다. 고로 import sys를 통해 sys.stdin.readline()로 값을 읽어온다.

 

첫 번째로 테스트 할 횟수를 입력받는다. 그 후 테스트할 횟수만큼 루프를 돌린다.

a,b 원소의 개수를 입력받고, a,b의 원소들을 입력받는다. 이 때 정렬을 해야한다. 그렇지 않으면 나중에 비교할 때 시간이 엄청 길어지게 된다.

 

정렬된 a,b 집합에서 a가 b보다 크면 result 변수에 +1을 해 준다.

그렇지 않으면 루프를 종료한다. 왜냐하면, 이미 정렬을 해 놨기 때문에 그 뒤는 다 b가 클 것이기 때문이다.

 

개수를 가진 변수 result를 출력하고, 값을 0으로 초기화 한다.

 

 

---

여담

Python3로 돌리면 시간 초과가 된다.

PyPy3로 돌려야 겨우 통과한다.

 

자료 구조를 배워야겠다.

시간 복잡도에 대해 공부해야 겠다.

 

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)