먹을 것인가 먹힐 것인가

문제 정보

• 사이트 : 백준 알고리즘 사이트
• 문제 번호 : 7795
• 문제 분류 : Two Pointer
• 난이도 : silver 3

문제 풀이

내가 짠 코드

• A가 B보다 큰 경우만 먹을 수 있으므로 A는 내림차순, B는 오름차순으로 정렬하여 반복문을 진행하였다.
• 만약 A중에서 B를 먹을 수 없는 경우가 나오면 그 뒤의 A는 해당 B를 먹을 수 없을 것이다(내림차순이므로)
• 이를 이용해 eat이라는 boolean 배열을 생성해 먹을 수 없는 B가 나오는 지점을 false로 바꿔 먹을 수 없다고 표시하여 반복하는 횟수를 줄였다.

public class BoJ7795 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            Integer[] arrA = new Integer[n];
            int[] arrB = new int[m];
            boolean[] eat = new boolean[m];
            input = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                arrA[i] = Integer.parseInt(input[i]);
            }
            input = br.readLine().split(" ");
            for (int i = 0; i < m; i++) {
                arrB[i] = Integer.parseInt(input[i]);
            }

            Arrays.sort(arrB);
            Arrays.sort(arrA, Collections.reverseOrder());
            Arrays.fill(eat, true);

            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if(!eat[j])
                        break;
                    if(arrA[i] > arrB[j])
                        count++;
                    else {
                        eat[j] = false;
                        break;
                    }
                }
            }
            System.out.println(count);
        }
        br.close();
    }
}

문제 출처

• 백준 먹을 것인가 먹힐 것인가

썸네일 출처

Image by storyset on Freepik