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

문제

 

문제 분석

- 시간 제한이 1초이므로 C++에서는 약 5억 번의 연산을 넘기면 안된다. 그런데, N과 M의 범위가 2만이므로, 다중 for문을 사용하게 되면 2억의 연산을 하게 된다. 이를 T 번 하게 되므로 시간 초과가 발생한다. 

- 처음에는 for 루프를 돌면서 A의 각각 숫자가 B의 숫자보다 크다면 +1을 하여 그 횟수를 세어주었다.

결론적으로, 아래와 같은 코드로 시간 초과를 받았다.

// 오답 코드 : 시간 초과 (테스트 케이스 개수가 정해지지 않았고 T * O(N^2) 연산에서 2억번 미만의 연산이 나오지 않을 가능성이 높다.
#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int T;
	// 입력부
	cin >> T;
	for (int i = 0; i < T; i++) { // 테스트 케이스 횟수만큼 진행
		vector<int> A;
		vector<int> B;
		int ans = 0; // A가 B보다 큰 쌍의 개수
		int N, M;
		cin >> N >> M;
		for (int i = 0; i < N; i++) { // A 배열 채우기
			int num;
			cin >> num;
			A.push_back(num);
		}
		for (int i = 0; i < M; i++) { // B 배열 채우기
			int num;
			cin >> num;
			B.push_back(num);
		}

		// A가 B보다 큰 쌍의 개수 구하기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (A[i] > B[j]) ans++;
			}
		}
		cout << ans << "\n";
	}

	return 0;
}

 

- A를 내림차순, B을 오름차순하여 A와 B중 A가 더 큰지 검사하는데, 정렬을 했으므로 B가 더 작아지거나 같아지는 시점부터는 더 이상 검사를 할 필요가 없다는 점을 이용하여 연산의 횟수를 줄였다. 

정답 코드

- 아슬아슬하게 통과를 받은 것 같은데, 추후 투 포인터나 이분 탐색으로 풀어볼 계획이다.

// 풀이 시간 : 41분 22초 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int T;
	// 입력부
	cin >> T;
	for (int i = 0; i < T; i++) { // 테스트 케이스 횟수만큼 진행
		vector<int> A;
		vector<int> B;
		int ans = 0; // A가 B보다 큰 쌍의 개수
		int N, M;
		cin >> N >> M;
		for (int i = 0; i < N; i++) { // A 배열 채우기
			int num;
			cin >> num;
			A.push_back(num);
		}
		for (int i = 0; i < M; i++) { // B 배열 채우기
			int num;
			cin >> num;
			B.push_back(num);
		}
		// A는 내림차순 정렬, B는 오름차순 정렬
		sort(A.begin(), A.end(), greater<int>());
		sort(B.begin(), B.end());

		// A가 B보다 큰 쌍의 개수 구하기
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (B[i] < A[j]) ans++;
				else break; // A와 B는 현재 정렬된 상태이므로, B가 A와 같아지거나 커지는 시점부터는 더 이상 검사를 할 필요가 없음 -> 연산의 횟수를 줄이기 위해 필요
			}
		}
		cout << ans << "\n";
	}

	return 0;
}

교훈점

- 정렬의 성질을 이용하여 완전탐색으로도 연산을 줄여 문제를 해결할 수 있었다.