[Kotlin] 백준 2591번 : 숫자카드 <Gold 5>

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

2591번: 숫자카드

 

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var number = readLine()

    val numList = mutableListOf<Int>()
    var count = 1

    // 연속된 숫자 찾기
    for (i in 0 until number.length-1){
        var now = number.slice(i .. i+1).toInt()
        if (now <= 34 && now >= 10) {
            count++
            if (number[i+1] == '0') count -= 2

            if (i == number.length-2) {
                numList.add(count)
            }
        }else{
            numList.add(count)
            count = 1
        }
    }

    // 연속된 숫자에 해당하는 배열 만들기
    val countList = mutableListOf<Int>(1,1,2)
    (3 .. numList.max()).map { countList.add(countList[it - 1] + countList[it - 2]) }


    bw.write("${numList.fold(1){sum, num -> sum*countList[num] }}")
    bw.flush()
    bw.close()
}

이게 내가 선택한 정답이고, 여기까지 도달하기까지의 과정은 아래와 같다. 

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

/*
var count: Int = 0

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var number = readLine()

    countCard(number)

    bw.write("$count")
    bw.flush()
    bw.close()
}


// 백트래킹 방식
fun countCard(number: String){
    if (number.slice(0 .. 1).toInt() <= 34) {
        if (number.length <= 3) count += 1
        else countCard(number.slice(2 until number.length))
    }

    if (number.length <= 2) count += 1
    else countCard(number.slice(1 until number.length))
}

 */

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var number = readLine()

    val numList = mutableListOf<Int>()
    var count = 1

    // 연속된 숫자 찾기
    for (i in 0 until number.length-1){
        var now = number.slice(i .. i+1).toInt()
        if (now <= 34 && now >= 10) {
            count++
            if (number[i+1] == '0') count -= 2

            if (i == number.length-2) {
                numList.add(count)
            }
        }else{
            numList.add(count)
            count = 1
        }
    }

    // 연속된 숫자에 해당하는 배열 만들기
    val countList = mutableListOf<Int>(1,1,2)
    (3 .. numList.max()).map { countList.add(countList[it - 1] + countList[it - 2]) }


    bw.write("${numList.fold(1){sum, num -> sum*countList[num] }}")
    bw.flush()
    bw.close()
}



/*
ex) 27123

숫자를 입력받음.

백트래킹을 사용함. 앞에서부터 34이하면 묶어버림. 그리고 뒷부분을 다시 묶어버릴지 선택 후 묶기 반복
마지막일때 돌아온다는 것을 파악하는 방법은? : 묶거나, 안묶는다고 판단한 후 뒤에 길이가 1 혹은 0이면 끝

27 12 23

27 : 34보다 작으니까 묶음
12 : 34보다 작으니까 묶음
=> 27 12 3

12를 묶기 전으로 이동하여 1을 따로 뺌
23 : 34보다 작으니까 묶음
=> 27 1 23

23을 묶기 전으로 이동하여 2를 따로 뺌
=> 27 1 2 3

27을 묶기 전으로 이동하여 7을 따로 뺌
71 : 34보다 크니까 안묶음
12 : 34보다 작으니까 묶음
=> 2 7 12 3

12를 묶기 전으로 이동하여 1을 따로 뺌
23 : 34보다 작으니까 묶음
=> 2 7 1 23

23을 묶기 전으로 이동하여 2를 따로 뺌
=> 2 7 1 2 3

==> 총 6개.


------------------------------------ 메모리 초과

하나씩 다 해보는 방법은 아닌것 같다. 규칙을 찾아볼까?


연속된 34이하의 숫자 만들 수 있는 경우들
1개 : 1개
2개 : 2개
3개 : 3개
4개 : 5개
5개 : 8개
6개 : 13개

1과 2는 기본적으로 셋팅해두자.
규칙 : f(n) = f(n-1) + f(n-2), (n>3)

연속된거 3개에, 2개짜리 하나 -> 6개 예상

ex)123912
12 3 9 12
12 3 9 1 2
1 23 9 12
1 23 9 1 2
1 2 3 9 12
1 2 3 9 1 2
=> 6개

가설 검증 완료


연속된 숫자를 판별하는 방법
: 0번Index와 1번 Index를 합쳐서 비교 : 가능하면 bool = true. count += 1
-> bool == true  숫자 1늘려서 1과 2 비교 : 반복
-> bool == false arr에 넣음. count = 0
입력받은 값 끝날때까지 반복

------------------------------------ 틀렸습니다.

0을 고려안했다.

예를들어 220일 경우

2 20
22 0
2 2 0

으로  분리를 시키고 있다.

0을 고려한 알고리즘을 만들어보자.
마지막에 0이 나오면 count - 2

22023
22 20 02 23

2 20 23
2 20 2 3

20 11 30 1
20 1 1 30 1

2103011
2 10 30 11
2 10 30 1 1
 */

---

첫번째 사고의 과정은 백트래킹이다. 

첫번째 숫자와 두번째 숫자가 34이하일 경우 묶어버리고, 그 다음 숫자로 다시 함수를 실행시킨다.

그 후 해당 숫자의 끝까지 갈때까지 반복한다.

 

이 과정은 당연하게 타임아웃.

 

타임아웃을 해결하기 위해서 규칙을 찾아보자.

생각해본다면 34이하인 숫자가 하나 있다면, 붙이거나 떼거나. 둘 중 하나의 경우이다. 그리고 떨어져 있는 34이하의 숫자가 2개 있다면 2*2로 4개의 방법이 만들어진다. 그렇다면 매번 끝까지 갈 필요가 없이 34이하의 숫자의 갯수를 세고, 곱해주면 된다.

 

이때 문제점이 하나 생겼다. 123과 같이 12도 되고 23도 되는 경우에는 2*2로 계산할 수 없다는 것이다. 그래서 3,4,5,6개일때를 손으로 직접 계산해보니 규칙이 보였다.

 

f(n) = f(n-1) + f(n-2) 단, n >= 3

 

이러한 규칙을 활용해서 문제를 풀어보았다.

 

34이하의 숫자는 입력받은 값의 길이만큼 반복을 하며 34이하가 나오면 count를 늘리고, 34이하가 되지 않는 수가 나온다면 지금까지 쌓인 count를 numList에 저장을 하고 count를 초기화 해준다. 이렇게 되면 numList에는 연속된 숫자의 길이가 저장되고, 그 길이중 가장 긴 값으로 규칙을 활용해 countList 내부를 채워준다.

 

그 후 numList의 숫자에 대응하는 countList의 값의 곱을 해주면 끝.

 

근데 틀렸다고 한다. 왜그럴까 생각을 하다보니 0을 고려하지 않았다는 생각이 들었다.

220을 예로 들면, 내가 위에 적은 방식은

22 0

2 20

2 2 0

이렇게 3개로 분리를 한다.

 

하지만, 카드는 0이 존재하지 않기 때문에 2 20 으로밖에 분리하지 못한다. 그렇기 때문에 0을 발견했을때의 상황을 부여해줬다.

 

0을 고려한 조건을 작성해주자.

우선 숫자가 10보다 작을때는 09 이런식이라는 것이다. 그렇기 때문에count를 늘려주지 않고 바로 numList에 저장하고, count를 초기화했다. 그리고 0으로 끝날때는 count를 -2해줬다. 과학적인 원리는 모르겠고 220이 3이 아닌 1이길래 -2를 해봤다.

 

그 후 위에했던 방식 그대로 작동시키니까 통과했다.

 

 

다른사람들은 DP를 통해서 구하더라. 값을 하나씩 넣으면서 연산하는 방식을 사용하던데 어떻게 그런 생각을 하는지...

오랜만에 골드 수준 문제를 푸니까 어렵다. 감 다뒤졌네

 

프로그래머스 Lv.0 빨리 졸업하고 어려운걸로 올라가야겠다.