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

문제

 

 

접근 방식

문제를 본 순간 떠올릴 수 있는 가장 쉬운 풀이는

배열을 하나하나 다 비교해 보는 것인데

두 배열의 최대 크기가 20000이기 때문에

최악의 시간 복잡도가 20000^2라 해당 문제를 풀 수가 없다.

 

투 포인터를 사용하여 효율적으로 풀 수 있지만

아직 배우지 않았기 때문에 정렬만 사용해서 풀어보기로 했다.

 

우선 두 배열을 모두 오름차순으로 기본 정렬한 후에

먹히는 배열을 순회하면서 먹는 배열을 매번 순회해 준다.

 

이때 먹히는 배열의 값이 먹는 배열의 값보다 작아지는 시점부터는

뒤에 오는 배열의 값들은 확인할 필요가 없기 때문에

남은 배열의 크기만큼 카운트를 추가해 주면 된다.

 

이렇게 풀면 시간은 오래 걸려도 통과는 되긴 하지만

나중에 이분탐색을 배운 후에 다시 풀이를 추가하도록 하겠다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			Integer[] a = new Integer[n];
			Integer[] b = new Integer[m];

			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				a[j] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				b[j] = Integer.parseInt(st.nextToken());
			}

			Arrays.sort(a);
			Arrays.sort(b);

			int count = 0;
			int max = a[n - 1];

			for (int j = 0; j < m; j++) {
				int num = b[j];
				if (num >= max) break;
				for (int k = 0; k < n; k++) {
					if (num >= a[k]) continue;
					count += n - k;
					break;
				}
			}

			sb.append(count).append("\n");
		}

		System.out.println(sb);
	}
}