이번 글에서는 두 개의 숫자 start와 end가 주어졌을 때, [start, end] 범위(양 끝값 포함)에 속하면서 자릿수가 연속적으로 증가하는 모든 숫자를 정렬된 리스트 형태로 찾는 방법을 알아보겠습니다.
연속적으로 증가하는 숫자란?
연속적으로 증가하는 숫자란 각 자릿수가 왼쪽에서 오른쪽으로 갈수록 정확히 1씩 커지는 수를 의미합니다. 예를 들어 5678은 5 → 6 → 7 → 8로 연속적으로 증가하므로 해당되지만, 169는 1과 6 사이가 연속적이지 않으므로 해당되지 않습니다.
문제 예시
입력이 다음과 같다고 가정해 보겠습니다.
- start = 10
- end = 150
그러면 출력 결과는 다음과 같습니다.
[12, 23, 34, 45, 56, 67, 78, 89, 123]
12부터 89까지의 숫자들과 123은 자릿수가 연속적으로 증가하고, 주어진 범위 안에 속하기 때문입니다.
풀이 접근 방법
이 문제를 해결하기 위한 핵심 아이디어는 간단합니다. 자릿수가 연속적으로 증가하는 숫자는 반드시 문자열 "123456789"의 부분 문자열에 해당한다는 점을 이용하는 것입니다.
단계별로 살펴보면 다음과 같습니다.
- 숫자 1부터 9까지를 이어 붙인 문자열 s = "123456789"를 준비합니다.
- 결과를 저장할 빈 리스트 a를 생성합니다.
- 첫 번째 인덱스 i를 0부터 8까지 반복합니다.
- 두 번째 인덱스 j를 i + 1부터 9까지 반복하며 부분 문자열을 추출합니다.
- 추출한 부분 문자열을 정수로 변환한 값 x가 start ≤ x ≤ end 조건을 만족하면 리스트 a에 추가합니다.
- 모든 반복이 끝나면 리스트 a를 오름차순으로 정렬하여 반환합니다.
이 방법의 시간 복잡도는 O(1)에 가깝습니다. "123456789"로 만들 수 있는 부분 문자열의 개수는 최대 45개로 고정되어 있기 때문에, 입력 범위가 아무리 커도 성능 저하 없이 빠르게 답을 구할 수 있습니다.
Python 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(start, end):
s = "123456789"
a = []
for i in range(9):
for j in range(i + 1, 10):
x = int(s[i:j])
if start <= x <= end:
a += (x,)
return sorted(a)
start = 10
end = 150
print(solve(start, end))입력
10, 150
출력
[12, 23, 34, 45, 56, 67, 78, 89, 123]
코드 설명
s[i:j]는 문자열 s에서 인덱스 i부터 j-1까지의 부분 문자열을 의미합니다. 예를 들어 i=0, j=3이면 "123"이 추출되고, 이를 int()로 변환하면 정수 123이 됩니다. 이 값이 주어진 범위 내에 있으면 리스트에 추가하고, 마지막에 sorted() 함수를 사용해 오름차순으로 정렬하여 반환합니다.
이처럼 브루트포스 방식으로 가능한 모든 연속 증가 숫자를 미리 생성한 뒤 범위 조건만 검사하면 되므로, 복잡한 자릿수 분석 없이도 깔끔하게 문제를 해결할 수 있습니다.