[백준/Kotlin] 1515번. 수 이어 쓰기

문제

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

 

 

 

풀이

234015가 입력으로 주어졌을 때 아래처럼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

밑줄 그어진 수가 입력으로 주어진 남은 수,

그렇지 않은게 다솜이가 지워린 수인것을 알 수 있고 마지막 값인 15가 정답이다. 

 

최소인 마지막 값을 찾으려면

1부터 1씩 증가시키면서 입력으로 주어진 수( 234015 )의 앞부터 지워나가면 된다.

 

순차적으로 생각하면 다음과 같다.

1 -> 234015

2 -> 234015, 2 삭제

3 -> 34015, 3 삭제

4 -> 4015, 4 삭제

5 -> 015

6  -> 015

7  -> 015

8  -> 015

9  -> 015

10 -> 015, 0 삭제

11 -> 15, 1 삭제

12 -> 5

13  -> 5

14 -> 5

15 -> 5, 5 삭제

 

이때 234015 를 deque에 저장해 직접 왼쪽부터 지워나가도 되나 지워진 곳의 인덱스만 기록해서 처리 하는게 빠르다.

 

한가지 주의사항으로 아래의 예시와 같이 비교하고있는 숫자가 커질 경우를 생각해보자

.. 생략 ...  

200 -> 221099, 2 삭제

201 -> 21099, 21 삭제

202 -> 099, 0 삭제

.. 생략 ...  

 

1씩 증가하면서 비교하고있는 200, 201, 202와 같은 수는 201 과 같이 중간에 일치하지 않는 수가 있어도 순서만 맞으면 삭제가 가능하다는 점을 유의해야한다.

 

 

 

정답 코드

fun main() {
    val removedNums = readln()
    var searchIndex = 0
    var num = 0

    while (searchIndex < removedNums.length) {
        num++
        val currentNum = num.toString()

        var i = 0  // current_num의 인덱스
        while (i < currentNum.length && searchIndex < removedNums.length) {
            if (currentNum[i] == removedNums[searchIndex]) {
                searchIndex++
            }
            i++
        }
    }

    println(num)
}

 

 

파이썬 버전의 풀이와 코드는 다음 포스팅 참조

[백준/Python] 1515번. 수 이어 쓰기