<백준> 신기한 소수(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%EC%8B%A0%EA%B8%B0%ED%95%9C%20%EC%86%8C%EC%88%98

[백준]

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

제출 결과

 

아주 쉽게 보고 접근했다가 메모리 초과 폭탄을 무지하게 많이 맞은 문제였다.(틀린 코드들은 깃허브에 다 남아있다.)

이 문제를 통해서 백트래킹을 할 때도 어떻게 가지치기를 해야할지 생각해보게 되었고 소수의 특성에 대해서도 좀 더 알게 되었다.

 

문제를 보고는 바로 2로 시작하는 숫자부터 해야겠다 싶었다.

4자리면 2000, 6자리면 200000

왜냐하면 1은 소수가 아니기 때문에 어짜피 걸러지기 때문이다.

하나씩 하나씩 순회를 하면서 왼쪽부터 1자리부터 n자리까지 소수 판별을 하고 소수가 아니면 다음 숫자로 넘어가도록 했다.

그리고 제출했더니 앞에서 말했다시피 메모리초과가 나왔다.

 

여기서 메모리초과를 잡기위해 한 방법은 무한루프를 수정한 것이다.

내가 예제만 보고 최대 길이를 5로 잡아버리는 사소하지만 큰 실수를 했다는 것을 코드를 다시 보면서 확인했다.

그리고 제출했더니 앞에서 말했다시피 메모리초과가 나왔다.

 

여기서 메모리초과를 잡기위해 한 방법은 가장 왼쪽 숫자에 대한 가지치기를 진행한 것이다.

생각해보면 가장 왼쪽 숫자가 2,3,5,7에 속하지 않는다면 조건에 처음부터 맞지 않는다는걸 알 수 있다.

그래서 이 부분을 추가했다.

그리고 제출했더니 앞에서 말했다시피 메모리초과가 나왔다.

 

사실 가지치기를 했다고 생각했지만 지금 돌아보면 어쨌든 모든 경우를 다 돌더라

숫자가 4로 시작한다고 4로 시작하는 케이스를 한 번에 뛰어넘게 짜지 않았기 때문이다...

이제 내가 짠 방식에 대한 불신이 생기기 시작하고 마지막으로 메모리초과를 잡기위해 한 방법은 한 블로그에서 본 소수의 특성을 보고 시도한 방법이었다.

- 1자리 소수는 2, 3, 5, 7 뿐이다.
- 2자리 이상의 소수는 반드시 1, 3, 7, 9로만 끝난다.(5이거나 짝수이면 5나 2로 나뉘기 때문이다.)

바로 1,3,7,9에 대한 가지치기를 진행하는 것이었다.

약간의 자신감이 생긴채로 제출했더니 앞에서 말했다시피 메모리초과가 나왔다.

 

이제는 이렇게 하나씩 순회하면서 하는 방식말고 다른 방식을 해봐야겠다는 생각이 들었다.

그리고 그 방법은 위의 두 가지 특성만을 이용하는 방식이었다.

재귀를 사용했고 StringBuilder를 적극적으로 활용했다.

전체적인 흐름은 같지만 세부적인 모양이 좀 다르다.

기존에는 숫자를 하나씩 올렸지만 이제는 첫번째 특성의 숫자로만 시작하게 리스트를 만들어 순회했고 이를 StringBuilder에 추가시켜 재귀함수를 시작했다.

그리고는 두번째 특성의 숫자 리스트를 순회하며 숫자를 넣었을 때 소수인지 판별하고 소수라면 최대 길이까지 재귀함수를 호출하도록 했다.

최대길이라면 결과 StringBuilder에 저장했다.

소수가 아닌 경우에는 그냥 넣은 숫자를 빼주고 지나갔다.

 

숫자 문제이다보니 숫자를 쓰는 거에만 집착을 해서 문자열로 가능할 거라는 거까지 가는데 너무 오래 걸렸다.

이런 문제를 안 풀어봤던 게 아닌데 머리가 좀 많이 굳어있는 거 같다.

말랑말랑하게 할 필요가 있다.

 

해당 방법으로 작성한 코드는 다음과 같다.

val result = StringBuilder()
fun main() = with(System.`in`.bufferedReader()) {
    val n = readln().toInt()
    val startList = listOf(2, 3, 5, 7)
    for (i in 0..3) {
        checkPosition(n, StringBuilder().append(startList[i]))
    }

    println(result)
}

fun checkPosition(length: Int, sb: StringBuilder) {
    if (sb.length == length) {
        result.append(sb).append("\n")
        return
    }

    val canUseList = listOf(1, 3, 7, 9)
    for (i in 0..3) {
        if (checkPrimeNumber((sb.append(canUseList[i]).toString()).toInt())) {
            checkPosition(length, sb)
        }
        sb.deleteCharAt(sb.lastIndex)
    }
}

fun checkPrimeNumber(num: Int): Boolean {
    var i = 2
    while (i * i <= num) {
        if (num % i++ == 0) return false
    }
    return true
}

 

<참고>

https://velog.io/@pds0309/%EB%B0%B1%EC%A4%80-2023-%EC%8B%A0%EA%B8%B0%ED%95%9C-%EC%86%8C%EC%88%98-java