BOJ) 작은 수 내기

작은 수 내기

16471번: 작은 수 내기

풀이

 

예전 문제들은 뭘 풀었는지 보다가, 이전에 작성했던 코드가 테스트 케이스 개편으로 시간 초과가 떠있는 것을 확인했다.

시간 초과를 그대로 두기에는 조금 찝찝해서 다시 풀어봤다.

 

각자 N장의 카드를 받는다. (N은 홀수다) 

2. 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다)

3. 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 경우, 둘 다 점수를 획득하지 못한다)

4. 총 N번의 승부 후, (N+1)/2점 이상의 점수를 획득한 사람이 승리한다.

5. (N+1)/2점 이상의 점수를 획득한 사람이 없을 경우, 승자가 없는 것으로 게임이 끝난다. 

 

우선, 사장님과 주언이의 덱을 저장하고 오름차순으로 정렬해주었다.

위의 문제 조건에 맞추기 위해, 주언이의 덱에서 가장 낮은 숫자가 사장님의 정렬된 덱에서 몇번 째 카드부터 이길 수 있는지 확인했다.

사장님의 덱을 순환할 때는 같은 숫자를 이길 수 없도록 이전에 이겼던 카드 이후부터 탐색해주었다.

 

탐색하면서 point가 이길 수 있는 조건이 되면 break를 걸어주어 탐색의 시간을 줄여줬다.

탐색이 종료되고, 주언이가 얻은 point가 이길 수 있는 조건의 point면 "YES" 를, 아니면 "NO"를 출력해줬다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int[] myArr = saveNumArr(size, new StringTokenizer(br.readLine()));
        int[] enemyArr = saveNumArr(size, new StringTokenizer(br.readLine()));

        br.close();
        solution(size, myArr, enemyArr);
    }

    private static void solution(int n, int[] myArr, int[] enemyArr) {
        Arrays.sort(myArr);
        Arrays.sort(enemyArr);

        int winPoint = (n+1)/2;
        int myPoint =0;

        int enemyIdx=0;
        for(int i=0; i<n; i++) {
            for(int j=enemyIdx; j<n; j++) {
                if(myArr[i] <enemyArr[j]) {
                    myPoint++;
                    enemyIdx = j+1;
                    break;
                }
            }
            if(myPoint == winPoint) break;
        }

        if(myPoint == winPoint)     System.out.println("YES");
        else                        System.out.println("NO");
    }

    private static int[] saveNumArr(int size, StringTokenizer st) {
        int[] arr = new int[size];
        for(int i=0; i<size; i++) arr[i] = Integer.parseInt(st.nextToken());
        return arr;
    }
}