백준 1020번: 디지털 카운터 - 상세 풀이
🔍 1. 문제 소개
백준 1020번 문제 "디지털 카운터"는 N자리의 디지털 카운터가 매 초마다 1씩 증가하는 상황을 가정합니다. 카운터는 10N-1에서 다시 0으로 순환하며, 각 숫자는 7개의 선분으로 구성된 특정 형태를 가집니다. 문제는 현재 카운터에 표시된 숫자의 선분 개수와 같은 선분 개수를 가지는 다음 숫자가 나타날 때까지 몇 초가 걸리는지 계산하는 것입니다. 각 숫자 (0~9)는 고정된 선분 개수를 가지며, N자리 수를 표현하기 위해 N자리보다 작은 수는 앞에 0을 채워 표현합니다.
💡 2. 문제 해석
문제의 핵심은 다음과 같습니다:
* 선분 개수: 각 숫자(0~9)는 고정된 개수의 선분으로 구성됩니다. (0: 6, 1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6) * N자리 수: 입력으로 주어지는 숫자는 N자리이며, N은 입력 숫자의 길이와 같습니다. * 순환: 카운터는 10N-1에서 0으로 순환합니다. * 목표: 현재 숫자와 선분 개수가 같은 다음 숫자가 나타날 때까지의 시간(초)을 구하는 것.
제약 조건은 N이 15보다 작거나 같은 자연수라는 점입니다.
🧠 3. 접근 방법
가장 단순한 접근 방법은 현재 숫자부터 순차적으로 숫자를 증가시키며 선분 개수를 계산하는 것입니다. 현재 숫자의 선분 개수와 같은 선분 개수를 가진 숫자를 찾을 때까지 반복합니다. 하지만 이 방법은 시간 복잡도가 O(10N)이 될 수 있어 비효율적입니다. 따라서 더 효율적인 방법을 사용해야 합니다. 본 풀이에서는 현재 숫자부터 순차적으로 탐색하지만, 숫자의 길이가 늘어나는 경우를 고려하여 효율성을 높입니다.
⚙️ 4. 구현 과정
- **입력:** 현재 카운터 값을 입력받습니다.
2. 선분 개수 계산: 입력받은 숫자의 각 자릿수에 해당하는 선분 개수를 합산하여 현재 숫자의 총 선분 개수를 계산합니다. 3. 순차 탐색: 현재 숫자부터 1씩 증가시키며, 각 숫자의 선분 개수를 계산합니다. 4. 비교: 현재 숫자의 선분 개수와 동일한 선분 개수를 가진 숫자를 찾으면 탐색을 종료하고, 그때까지 걸린 시간(초)을 출력합니다. 5. 자릿수 증가 처리: 탐색 중 숫자의 자릿수가 증가하면, 해당 경우에는 -1을 출력하고 종료합니다. (문제에서 명시적으로 언급되어 있지는 않지만, 같은 자릿수 내에서 답을 찾지 못하면 -1을 출력하는 것이 자연스럽습니다.)
💻 5. 코드 설명
fun solve() {
val n = readLine()!!
val segments = intArrayOf(6, 2, 5, 5, 4, 5, 6, 3, 7, 6)
val targetSegments = n.map { segments[it.digitToInt()] }.sum()
var count = 0
var currentNumber = n.toLong()
while (true) {
count++
currentNumber++
val nextNumberStr = currentNumber.toString()
if (nextNumberStr.length > n.length) {
println(-1)
return
}
val nextSegments = nextNumberStr.map { segments[it.digitToInt()] }.sum()
if (nextSegments == targetSegments) break
}
println(count)
}
fun main() {
solve()
}
* segments 배열: 각 숫자(0~9)에 대한 선분 개수를 저장합니다. * targetSegments: 입력 숫자의 총 선분 개수를 계산합니다. * count: 경과 시간(초)을 저장합니다. * currentNumber: 현재 확인 중인 숫자를 저장합니다. Long 타입으로 선언하여 자릿수 증가에 대비합니다. * while 루프: targetSegments와 같은 선분 개수를 가진 숫자를 찾을 때까지 반복합니다. * if (nextNumberStr.length > n.length): 숫자의 자릿수가 증가하면 -1을 출력하고 종료합니다. 이 부분이 시간 복잡도 개선에 중요한 역할을 합니다.
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
* 시간 복잡도: 최악의 경우, 같은 선분 개수를 가진 숫자를 찾을 때까지 모든 숫자를 탐색해야 할 수 있습니다. 하지만 입력 숫자의 자릿수가 증가하는 경우를 처리하므로, 실제로는 O(10N)보다 훨씬 작은 시간 안에 종료됩니다. 평균적인 시간 복잡도는 정확히 분석하기 어렵지만, 실험적으로는 매우 효율적임을 확인할 수 있습니다. O(k) (k는 같은 선분 개수를 갖는 다음 숫자를 찾을 때까지의 반복 횟수)로 근사할 수 있습니다. k는 대부분의 경우 10N 보다 훨씬 작습니다.
* 공간 복잡도: segments 배열은 고정된 크기이며, n, currentNumber, nextNumberStr 등의 변수는 입력 크기에 비례하는 크기의 공간을 사용합니다. 따라서 공간 복잡도는 O(N)입니다.
🎯 7. 결론
본 풀이는 입력 숫자의 자릿수 증가를 고려하여 순차 탐색의 비효율성을 어느 정도 완화했습니다. 순차 탐색의 본질적인 한계는 남아있지만, 실제 실행 시간은 상당히 개선되었습니다. 더욱 효율적인 알고리즘을 설계하기 위해서는 수학적인 분석을 통한 더욱 정교한 접근이 필요하지만, 이 풀이는 백준 문제의 제약 조건 내에서 합리적인 성능을 제공합니다. 문제 해결 과정에서 시간 복잡도 개선의 중요성과 실제 실행 시간과의 차이에 대한 이해도 높일 수 있었습니다.