[알고리즘] 리모컨 (백준 1107번)

1107번: 리모컨

 시뮬레이션 문제인데 solved.ac 티어는 골드 5인데 그에 비해 정답률이 20% 대로 낮은 편이다. 실제로 나도 풀이 방향을 잘못 잡아서 시간이 엄청 오래 걸렸다.

 

Solution

 우선 리모컨의 부서지지 않은 숫자 버튼들을 최대한 눌러서 N에 최대한 가까운 수를 만들어서 클릭 수를 계산해야 된다. 

 

1. 먼저 나올 수 있는 최대 경우의 수(max_value)를 구한다. 이 때 최대 경우의 수라 함은 N 이상인 수 중에 나올 수 있는 최소값을 의미한다. 
2. 0~max_value 까지 반복문을 돌린다
3. 총 클릭 수 = 숫자 자리 수 + (N과 현재 숫자 차이)
4. EX) N : 100, 현재 값 : 87 -> 2 + 13 = 15번이 총 클릭 수가 된다.
5. max_value까지 수 중 총 클릭 수가 가장 낮은 수를 구하여 min에 저장한다.
6. min을 출력한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.HashSet
import kotlin.math.abs
import kotlin.math.min

fun solution(){

    var isBroken = BooleanArray(10)

    val N_str = readLine()!!
    val N = N_str.toInt()
    val M = readLine()!!.toInt()


    //부서진 버튼이 있다면
    if(M > 0)
    {
        var str = readLine()!!

        for(i in 0 until str.length step 2)
            isBroken[str[i] - '0'] = true
    }

    var range = (0..9).filter { i -> !isBroken[i] }

    var range_set = HashSet<Int>(range)

    var max_value = getMaxValue(N, range_set)

    var min = abs(N - 100)

    for(i in (0 .. max_value).filter { i ->
        for(c in i.toString())
        {
            if(!range_set.contains(c-'0'))
                return@filter false
        }
        true
    })
    {
        var str = i.toString()

        min = min(str.length + abs(N - i), min)

        if(i == N)
            break
    }

    print(min)

}

fun getMaxValue(N : Int, range_set : HashSet<Int>) : Int
{
    for(i in N .. 1000000)
    {
        var isFinish = true
        for(c in i.toString())
        {
            if(!range_set.contains(c-'0'))
            {
                isFinish = false
                break
            }
        }

        if(isFinish)
            return i
    }
    return 1000000
}


fun main() {
    solution()
}