백준 - 십자카드 문제(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

주어진 숫자로 만들 수 있는 시계수가 몇번째 시계수인지 구하는 문제

 

[접근 방법]

완전탐색으로 1111~9999까지 모든 시계수를 만들기.

시간복잡도는 9*9*9*9(모든숫자)*4*4(시계수 만들기)

 

[처음 작성한 답안]

import java.io.BufferedReader
import java.io.InputStreamReader

// 현재 몇번째 시계수인지 체크
var idx = 0
// 이미 체크한 시계수인지 체크
val isVisited = BooleanArray(10000)
// 입력으로 만들 수 있는 시계수
var targetNumber = 0

fun main(): Unit = with(BufferedReader(InputStreamReader(System.`in`))){
    val numbers = readLine().split(" ").map {it.toInt()}.toIntArray()
    targetNumber = makeClockCount(numbers)

    println(recursion(numbers, IntArray(4), 0))
}

// 시계수 만들기
fun makeClockCount(numbers: IntArray): Int {
    var answer = Int.MAX_VALUE

    for (j in 0..3) {
        var currentNumber = 0
        for (i in 0..3) {
            currentNumber *= 10
            currentNumber += if (j+i > 3) {
                numbers[j + i - 4]
            } else {
                numbers[j + i]
            }
        }
        answer = currentNumber.coerceAtMost(answer)
    }

    return answer
}

fun recursion(numbers: IntArray, currentNumbers: IntArray, currentIdx: Int): Int {
    // 4자리수를 만들었으면 시계수로 만들어보기
    if (currentIdx == 4) {
        val clockCount = makeClockCount(currentNumbers)

        // 이미 만들었던 시계수면 현재 시계수 개수는 증가하지 않고
        // 만들지 않았던 시계수면 개수가 증가하고 방문처리함
        if (!isVisited[clockCount]) {
            idx++
            isVisited[clockCount] = true
            // 만약 입력으로 받은 시계수와 같은 값이면 현재 개수가 시계수의 인덱스
            if (clockCount == targetNumber) {
                return idx
            }
        }

        return -1
    }

    // 1111~9999까지 만들기
    for (i in 1..9) {
        currentNumbers[currentIdx] = i
        
        // idx가 -1이 아니면 시계수를 찾은 것이므로 idx return
        if (recursion(numbers, currentNumbers, currentIdx+1) != -1) {
            return idx
        }
    }

    return -1
}

다른 사람들 풀이를 보니까 나머지나 나눗셈 연산을 이용해서 숫자를 1자리씩 이동하는 방법을 사용해줬다.

따라서, 비슷하게 짜본 코드

 

[보완한 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

var idx = 0
val isVisited = BooleanArray(10000)
var targetNumber = 0

fun main(): Unit = with(BufferedReader(InputStreamReader(System.`in`))){
    val inputs = readLine().split(" ").map {it.toInt()}
    var number = inputs[0]*1000+inputs[1]*100+inputs[2]*10+inputs[3]
    targetNumber = makeClockCount(number)

    println((recursion(number, 0,0)))
}

fun makeClockCount(number: Int): Int {
    var temp = number
    var minNum = number
    // 나머지와 나누기로 1자리씩 이동하기
    repeat(3) {
        temp = temp % 1000 * 10 + temp / 1000
        if(minNum > temp) minNum = temp
    }
    return minNum
}

fun recursion(number: Int, currentNumber: Int, currentIdx: Int): Int {
    if (currentIdx == 4) {
        val clockCount = makeClockCount(currentNumber)

        if (!isVisited[clockCount]) {
            idx++
            isVisited[clockCount] = true
            if (clockCount == targetNumber) {
                return idx
            }
        }

        return -1
    }

    for (i in 1..9) {
        var addedNum = 1000
        repeat(currentIdx) {
            addedNum /= 10
        }

        if (recursion(number, currentNumber + addedNum*i, currentIdx+1) != -1) {
            return idx
        }
    }

    return -1
}