백준 - 2503 : 숫자 야구(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2503

 

[문제 설명]

숫자 야구를 한다.

N번의 시도를하고 그 결과를 바탕으로 추론할 다음 숫자를 구하시오.

 

[접근 방법]

최적화 된 답안이 없어 보인다. 따라서, 브루트포스를 생각해봤다.

3자리 순열을 만드는데 (9^3).

그래서 만들어진 순열의 개수는 9P3 = 9 * 8 * 7 = 504

순열과 모든 정답을 비교해야 하므로 O(n * 순열의 개수)

따라서, 최종 시간복잡도는 O(n*순열의 개수)가 된다.

n은 1 이상 100 이하이므로 연산 횟수는 충분히 여유가 있다.

 

[코드]

val permutation = ArrayList<Int>()
val visited = BooleanArray(10)
fun main() {
    val n = readln().toInt()
    val arrOfBall = IntArray(n)
    val arrOfStr = IntArray(n)
    val arrOfAnswer = IntArray(n)
    repeat(n) { idx ->
        val input = readln().split(" ").map { it.toInt() }
        arrOfAnswer[idx] = input[0]
        arrOfStr[idx] = input[1]
        arrOfBall[idx] = input[2]

        // if : 모두 스트라이크면 그 숫자가 정답이므로 유일한 정답이 됨.
        if (arrOfStr[idx] == 3) {
            println(1)
            return
        }
    }

    // 모든 경우의 수 만들기
    makePermutation(currentIdx = 0, 0)
    // 가능한 정답인지 체크 가능한 정답이면 true
    val isCanBeAnswer = BooleanArray(permutation.size) { true }
    for (i in permutation.indices) {
        // 정답이라고 가정하는 숫자
        val answer = permutation[i]
        // if : 정답이 될 수 없는 애면 넘어감.
        if (!isCanBeAnswer[i]) {
            continue
        }

        for (j in arrOfAnswer.indices) {
            // 추측하는 숫자
            val guessNum = arrOfAnswer[j]
            // 추측하는 스트라이크
            val guessStr = arrOfStr[j]
            // 추측하는 볼
            val guessBall = arrOfBall[j]
            // 현재 번호가 정답일 경우 볼과 스트라이크 개수
            val (str, ball) = getStrikeAndBall(guessNum, answer)

            // if : 예측이 일치하지 않으면 이건 정답이 될 수 없다.
            if (guessBall != ball || guessStr != str) {
                isCanBeAnswer[i] = false
                break
            }
        }
    }

    var cnt = 0
    isCanBeAnswer.forEach {
        if (it) {
            cnt++
        }
    }
    println(cnt)
}

fun makePermutation(currentIdx: Int, sum: Int) {
    if (currentIdx == 3) {
        permutation.add(sum)
        return
    }

    for (i in 1..9) {
        if (visited[i]) {
            continue
        }

        visited[i] = true
        makePermutation(currentIdx + 1, sum * 10 + i)
        visited[i] = false
    }
}

fun getStrikeAndBall(guessNum: Int, answer: Int): Pair<Int, Int> {
    var str = 0
    var ball = 0
    val cntOfNums = IntArray(10)
    val checkedNum = BooleanArray(10)
    var tempGuess = guessNum
    var tempNum = answer

    while (tempGuess > 0 && tempNum > 0) {
        if (tempGuess % 10 == tempNum % 10) {
            str++
        }
        cntOfNums[tempGuess % 10]++
        cntOfNums[tempNum % 10]--
        checkedNum[tempGuess % 10] = true
        checkedNum[tempNum % 10] = true
        tempGuess /= 10
        tempNum /= 10
    }

    checkedNum.forEachIndexed { index, b ->
        if (b && cntOfNums[index] == 0) {
            ball++
        }
    }
    ball -= str

    return str to ball
}