7795.md

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

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

---

코드 설명

• A에서 B보다 큰 수를 찾는 case 개수 구하기 -> 다만 전체 경우의 수를 세면 시간초과가 난다.
• A와 B를 먼저 정렬한 뒤 A가 B보다 큰 위치를 찾는게 이 문제의 중요 포인트이다. -> 개수보다는 위치에 초점을 맞춰야 한다.

소스코드

• 메모리 : 33248 KB
• 시간 : 184 ms

import sys

case = int(input())
result = []
while case:
	case -= 1
	count = 0
	n, m = map(int, sys.stdin.readline().split())
	A = list(map(int, sys.stdin.readline().split()))
	B = list(map(int, sys.stdin.readline().split()))
	A.sort(reverse=True)
	B.sort(reverse=True)
	index_a = 0
	index_b = 0
	while index_a < n and index_b < m:
		if A[index_a] > B[index_b]:
			count += m - index_b
			index_a += 1
		else:
			index_b += 1
	result.append(count)
	
for r in result:
	print(r)

오답 노트

• 가장 쉬운 방법으로는 완전 탐색이지만 시간초과가 난다. (파이썬만 시간초과나는 것 일수도 있음.)

오답 코드

import sys

case = int(input())
result = []
while case:
	case -= 1
	count = 0
	n, m = map(int, sys.stdin.readline().split())
	A = list(map(int, sys.stdin.readline().split()))
	B = list(map(int, sys.stdin.readline().split()))
	for a in A:
		for b in B:
			if a > b:
				count += 1
	result.append(count)
	
for r in result:
	print(r)