백준 7795 먹을 것인가 먹힐 것인가(Java)

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

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

---

 

해석 및 팁

 

---

 

이 문제를 풀 때 단순히 이중반복문을 사용하면 시간초과가 발생하므로 시간을 줄여줘야 합니다. 따라서 배열을 정렬한 후에 check배열을 뒤에서부터 검사했을 때 arr배열이 큰 값이 존재하면 check배열의 남은값은 모두 arr배열보다 작기 때문에 남은 개수를 count에 더 해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();
    
    for(int i = 0; i < t; i++) {
      int count = 0;
      int n = sc.nextInt();
      int m = sc.nextInt();
      int[] arr = new int[n];
      int[] check = new int[m];
      for(int j = 0; j < n; j++) arr[j] = sc.nextInt();
      for(int j = 0; j < m; j++) check[j] = sc.nextInt();

      Arrays.sort(arr);
      Arrays.sort(check);

      for(int j = 0; j < n; j++) {
        for(int k = m - 1; k >= 0; k--) {
          if(arr[j] > check[k]) {
            count += (k + 1);
            break;
          }
        }
      }
      sb.append(count + "\n");
    }
    
    System.out.println(sb);
  }
}