[백준 16566] - 카드게임(Kotlin)[플레5]

문제

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

16566번: 카드 게임

 

문제 풀이

문제가 길고, 부연 설명도 많은 편이지만,

한마디로 요약하자면 다빈치 코드라는 게임에서 이기는 최적의 경우를 계산한다고 생각하면 편할 것이다.

당연하게도 상대방이 낼 카드를 알고 있다면, 플레이어는 가장 근소하게 이기거나, 지는 걸 원할 것이다.

즉 문제의 목표는 상대방의 카드에 따라서 가장 적합한 카드를 찾는 것이다.

이렇게 문제를 이해하자마자 이분탐색이 떠올랐다.

내가 가지고 있는 카드 중에서 가장 적합한 카드를 탐색하는 과정에서 사용할 수 있는 이분탐색은 시간복잡도가 O(logN)이기 때문이다.

 

이분 탐색

private fun binarySearch(value: Int): Int {
    var left = 0
    var right = cards.size - 1
    var mid = 0
    while (left < right) {
        mid = (left + right) / 2
        if (cards[mid] <= value) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return right
}

 

카드와 가장 크면서 가까운 카드의 인덱스를 찾는 함수이다.

이렇게 적합한 카드를 찾았음에도 불구하고 신경 쓰이는 문제가 있었다.

 

사용한 카드에 대해서 어떻게 처리하냐였다.

 

사용한 카드 처리 방법

1️⃣ 새로운 boolean 배열을 생성해서 카드의 사용을 체크하는 방법

 

카드의 개수만큼 boolean 배열을 만들어서 사용했다면 탐색을 다시 하는 방법이지만,

이분탐색 내에서 계속해서 mid에 해당하는 배열을 조건문으로 검사하는 건 굉장히 비효율적이고, 이미 사용했다면

mid, left, right에 대한 연산에 대한 적절한 방법이 떠오르지 않았다.

 

2️⃣ 카드를 사용하고 리스트에서 제거하기

 

그래서 내가 선택한 방법은 카드를 사용했다면 리스트에서 제거하는 방법이다.

해당 방법을 사용할 경우 이분탐색에 대한 코드를 바꿔주지 않아도 문제가 없었다.

하지만 배열에서 원소를 삭제하는 것은 시간복잡도 측면에서 그렇게 효율적인 방법은 아니라고 생각은 했다.

해당 방법으로 코드를 제출했지만, 시간초과라는 결과가,,, 

어떻게 보면 당연한 결과이다. 매번 카드를 사용할 때마다 배열에 원소를 삭제하는 것은 굉굉 굉장히 비효율적인 방법이다.

 

3️⃣ Union & Find

 

적합한 카드의 후보를 연결하는 방법에 대해서 많은 고민을 해봤지만,

알고리즘 분류를 보니 분리집합이라는 단어가 있었고, 획기적인 방법이라고 생각이 들었다.

 

예를 들어서 내가 5라는 카드를 사용했다면, 다음번에도 적합한 카드로 5가 선택될 경우 5와 가장 가까운 카드를 유도하는 방법이다.

이러한 유도를 하는 과정에서 Union & Find가 사용되는데, 어떻게 사용되는지 살펴보자.

 

상대방이 내는 카드는  [1, 1, 1, 5, 5, 5]이고, 플레이어가 들고 있는 카드는 [1, 2, 3, 4, 6, 8, 10, 11]이라는 상황을 가정하자.

 

1. 상대방이 1을 내고, 플레이어는 2를 내서 이길 것이다.
2. 상대방이 1을 내고, 플레이어는 2와 가장 가까운 3을 내야 한다.

여기서 2->3으로 연결하는 과정에서 Union & Find가 사용된다.

코드를 통해서 살펴보자.

parent = IntArray(n){it}

기본적으로 집합의 우두머리를 뜻하는 parent는 자기 자신으로 초기화한다.

이분탐색의 결과로 우리는 3번 카드가 아닌 2번 카드의 인덱스를 반환할 것이다.

(카드를 없애지 않았기 때문)

그러면 2번의 부모를 계산한다.

만약 2번의 부모가 자기 자신이라면, 최초로 사용되었다는 뜻이다.

그 후 2번에서 가장 가까운 카드인 3번과 Union을 진행해서 2번의 부모를 3번의 부모로 옮겨준다.

해당 과정에서 parent [2] = parent [3]이 될 것이다.

 

만약 다음번에도 2번 카드가 선택된다면 2번 카드의 부모에 대항하는 3번이 선택될 것이고, 

parent [3] = parent [4]가 되는 것처럼 계속해서 카드가 가리키는 숫자를 확장시켜 주는 것이다.

 

이러한 방법으로 카드 사용에 대한 처리를 배열을 삭제, 추가하지 않고 처리할 수 있다.

 

전체 코드

import java.io.*
import java.lang.StringBuilder

class Solution {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private lateinit var cards: IntArray
    private lateinit var redCards: IntArray
    private lateinit var parent: IntArray
    private val sb = StringBuilder()

    init {
        input()
        playGame()
        print(sb.toString())
    }

    private fun input() {
        val (n, m, k) = br.readLine().split(" ").map { it.toInt() }
        parent = IntArray(n){it}
        cards = br.readLine().split(" ").map { it.toInt() }.toIntArray()
        cards.sort()
        redCards = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    private fun playGame() {
        for (card in redCards) {
            var idx = binarySearch(card) // 적절한 위치를 찾아주기
            idx = find(idx)
            sb.append(cards[idx]).append("\n")
            union(idx, idx + 1)
        }
    }

    private fun binarySearch(value: Int): Int {
        var left = 0
        var right = cards.size - 1
        var mid = 0
        while (left < right) {
            mid = (left + right) / 2
            if (cards[mid] <= value) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return right
    }

    private fun union(num1: Int, num2: Int) {
        val parent1 = find(num1)
        val parent2 = find(num2)
        if (parent1 < parent2) {
            parent[num1] = parent2
        } else {
            parent[num2] = parent1
        }
    }

    private fun find(value: Int): Int {
        if (value == parent[value])
            return value
        parent[value] = find(parent[value])
        return parent[value]
    }
}

fun main() {
    val solution = Solution()
}