백준 1107 리모컨 Kotlin (완전탐색)

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

1107번: 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

힌트

5455++ 또는 5459--

알고리즘 분류

• 브루트포스 알고리즘

반례

https://www.acmicpc.net/board/view/46120

풀이

본인은 처음엔 set과 순열 알고리즘을 사용해서 숫자를 눌러서 채널을 이동하는 경우의 수를 찾았다.

좋지 않은 접근 방법으로 시간 초과를 계속 겪다가 결국 통과는 했지만 2028ms...

코틀린은 역시 느리다며 언어 탓을 시전했으나 다른 사람들은 코틀린으로 100ms대로 푼 걸 봤다.

항상 문제는 나한테 있는데 ㅎㅎㅎ

다시 집중하고 코드를 리팩토링하여 156ms까지 줄였다.

생각해 보니 고장난 번호는 0에서 9까지 밖에 없고 중복도 없기 때문에

굳이 set을 사용할 필요도 없고 단순히 1차원 논리형 배열에 저장하면 된다.

조금이나마 메모리를 절약할 수 있고 시간 차이는 아마 배열이 조금 더 빠를 것 같은데 이는 한 번 공부해 봐야겠다.

핵심 풀이는, 수빈이가 이동하려는 채널이 최대 500000이니 최대 1000000 채널까지 검사하면 된다.

이보다 큰 채널은 검사할 필요가 없고, 찾는 채널보다 큰 채널을 검사하는 이유는 1500에서 2000을 가는 것보다

2300에서 1500을 가는 것이 더 빠르기 때문에, 즉 찾는 채널보다 작은 채널에서 출발한다고 해서 이동 횟수가 적은 게 아니기 때문에, 채널 0부터 1000000 채널까지 완전 탐색(BruteForce)해 준다.

 

 

코드(완전탐색)

import java.util.StringTokenizer
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.*

var answer=0
val nopeSet = mutableSetOf<Int>()
fun main() = with(System.out.bufferedWriter()) {
    //start 100
    val br = BufferedReader(InputStreamReader(System.`in`))
      val input = br.readLine()
    val goal = Integer.parseInt(input)
    val goalLen =input.length
    var n = Integer.parseInt(br.readLine())
    var answer = abs(goal-100)
    val nope = BooleanArray(10)
    if(n!=0) {
        val tk = StringTokenizer(br.readLine())
        while (n-- != 0) {
            nope[Integer.parseInt(tk.nextToken())]=true
        }
    }
    else{
        write("${min(goalLen,answer)}")
        close()
        return
    }

    if(n==10){
        write("$answer")
        close()
        return
    }
    for( i in 0 .. 1000000){
        var num =i
        var canCheck =true
        var cnt=0
        while(num>0){
            if(nope[num%10]){
                canCheck=false
                break
            }
            cnt++
            num/=10
        }
        if(i==0) {
            cnt = 1
            if(nope[i]) {
                canCheck = false
            }
        }
        if(canCheck){
            answer = min(answer, abs(goal-i)+cnt)
        }
    }
    write("$answer")
    close()
}

코드(순열)

import java.util.StringTokenizer
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.*

var answer=0
val nopeSet = mutableSetOf<Int>()
fun main() = with(System.out.bufferedWriter()) {
    //start 100
    val br = BufferedReader(InputStreamReader(System.`in`))
      val input = br.readLine()
    val goal = Integer.parseInt(input)
    val goalLen =input.length
    var n = Integer.parseInt(br.readLine())
    var answer = abs(goal-100)
    val nope = BooleanArray(10)
    if(n!=0) {
        val tk = StringTokenizer(br.readLine())
        while (n-- != 0) {
            nope[Integer.parseInt(tk.nextToken())]=true
        }
    }
    else{
        write("${min(goalLen,answer)}")
        close()
        return
    }

    if(n==10){
        write("$answer")
        close()
        return
    }
    for( i in 0 .. 1000000){
        var num =i
        var canCheck =true
        var cnt=0
        while(num>0){
            if(nope[num%10]){
                canCheck=false
                break
            }
            cnt++
            num/=10
        }
        if(i==0) {
            cnt = 1
            if(nope[i]) {
                canCheck = false
            }
        }
        if(canCheck){
            answer = min(answer, abs(goal-i)+cnt)
        }
    }
    write("$answer")
    close()
}