백준 : 7795번 먹을 것인가 먹힐 것인가(c++)

백준 링크

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	11886	5889	4392	49.903%

문제

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

입력

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

출력

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

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1

코드 풀이

이번 문제는 정렬 알고리즘 응용문제로 정렬을 이용해 풀이하는 문제였다.

• 입력으로 주어진 TestCase만큼의 반복문 실행
• 입력으로 주어진 N, M의 개수만큼 벡터 선언 후 resize
• vecB만 오름차순 정렬
• vecA, vecB를 탐색해야하기 때문에 2중 포문을 돌면서 vecA[i]가 vecB[j]보다 크다면 ++Anwer;

주의해야 할 부분

• A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램이기 때문에 무조건 vecB를 정렬해야 한다.
• 마지막 2중포문 돌릴 때 if문에 break를 하였는데 이 부분 continue를 하면 안 된다.(시간초과)

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int TestCase = 0;

	cin >> TestCase;

	while (TestCase--)
	{
		int N, M;

		cin >> N >> M;

		vector<int> vecA;
		vecA.resize(N);
		vector<int> vecB;
		vecB.resize(M);
		for (int i = 0; i < N; ++i)
		{
			cin >> vecA[i];
		}
		for (int j = 0; j < M; ++j)
		{
			cin >> vecB[j];
		}

		// vecB만 오름차순 정렬
		sort(vecB.begin(), vecB.end());

		int Answer = 0;

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				// vecA[i]번째 숫자가 vecB[j]숫자보다 작다면 무조건 break
				if (vecA[i] <= vecB[j])
					break;

				++Answer;
			}
		}

		cout << Answer << '\n';
	}

}