[백준] 16471번 : 작은 수 내기 (JAVA)

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

16471번: 작은 수 내기

 

풀이

 정렬, 그리디 문제이다.
조건을 문제에 다 적어줘서 그대로 구현만 하면된다.

주언이가 카드를 냈을 때 사장님이 낸 카드의 조건이 다음과 같아야 한다.
1. 주언이의 카드보단 숫자가 커야한다
2. 1조건에 부합하는 카드중 가장 작은 숫자여야 한다.

그래야 주언이가 이길 수 있는 최선의 로직을 탐색할 수 있다.

풀이 과정을 살펴보자

1. 먼저 주언이의 카드와 사장님의 카드를 오름차순으로 정렬해준다.
2. 그 후 주언이가 카드를 작은 숫자부터 낸다.
3. 사장님의 카드를 탐색하며 위에 조건이 만족하는 카드를 찾는다.

이중 for문의 시간복잡도는 O(N) 이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr1 = new int[N]; // 주언이 카드
        int[] arr2 = new int[N]; // 사장님 카드

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr1[i] = Integer.parseInt(st1.nextToken());
            arr2[i] = Integer.parseInt(st2.nextToken());
        }

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int winCount = 0;
        int idx = 0;

        for (int i = 0; i < N; i++) {
            if (winCount >= (N+1) / 2) break; // 해당 조건이 만족하면 더 이상 탐색할 필요가 없다.

            for (int j = idx; j < N; j++) {
                if (arr1[i] < arr2[j]) {
                    winCount++;
                    idx = j + 1;
                    break;
                }
            }

        }

        System.out.println(winCount >= (N+1) / 2 ? "YES" : "NO");
    }

}