[백준] 16566번 : 카드 게임 - 자바(JAVA)

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

16566번: 카드 게임

 

문제 해석

철수와 민수는 카드 게임을 즐겨한다.

 

1. N개의 빨간색 카드가 있으며 1부터 N까지 번호가 매겨져 있다.

2. N개의 파란색 카드가 있으며 1부터 N까지 번호가 매겨져 있다.

3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.

4. 철수와 민수는 고른 카드 중 1장을 뒤집어진 상태로 낸다.

5. 카드 번호가 큰 사람이 이기고 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다.

 

이때 카드는 각각 M개씩 뽑는다. (철수, 민수는 모두 같은 번호를 뽑음)

철수는 본인이 낼 카드를 마음대로 조작할 수 있다.

민수는 철수가 낼 카드를 알아낼 수 있다.

민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

 

 

문제 풀이 전 설계

N, M, K가 주어진다.

N = 카드의 개수

M = 카드의 번호

K = 게임 횟수

 

이후에 카드의 번호들이 주어진다.

이후에 철수가 i번째로 내는 카드의 번호가 주어진다.

 

즉, 철수가 내는 카드의 번호를 토대로 민수가 어떤 카드를 낼지 찾아야 하는 문제입니다.

 

문제에서는 카드를 내지 못하는 경우는 없다고 가정했습니다.

 

즉, 같은 행위를 K번 반복하는 문제이기 때문에 세그먼트 트리가 떠오릅니다.

 

민수가 내야 할 적절한 카드를 탐색하는 것을 O(N)으로 하면 시간 복잡도는 4,000,000 x 10,000 이기 때문에 트리를 형성하여 logN으로 줄여야 합니다.

 

하지만 굳이 세그먼트 트리를 하지 않아도 카드의 번호들을 한번 정렬해주고 이분 탐색으로 민수가 내는 카드를 탐색해도 풀리는 문제입니다.

 

코드

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

public class Main_16566_카드게임_SOL {
    static int n;
    static int m;
    static int k;
    static int[] cards;
    static int[] chulsu;

    public static int binarySearch(int target) {
        int left = 0;
        int right = m - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (cards[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right + 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        cards = new int[m];
        chulsu = new int[m];
        Set<Integer> minsu = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            chulsu[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);

        for (int i = 0; i < k; i++) {
            int pos = binarySearch(chulsu[i]);

            while (minsu.contains(pos)) {
                pos += 1;
            }
            minsu.add(pos);
            System.out.println(cards[pos]);
        }
        br.close();
    }
}