문제 개요
하나의 숫자 n이 주어졌을 때, 길이가 n+1인 소문자 문자열을 구성해야 합니다. 단, 임의 위치의 문자는 반드시 바로 뒤에 있는 문자보다 사전순(lexicographically)으로 커야 합니다.
예를 들어 입력이 15라면 출력은 ponmlkjihgfedcba입니다. 'p'에서 'a'까지 총 16개(= n+1)의 문자가 알파벳 역순으로 배열되어 있어, 모든 위치에서 현재 문자가 다음 문자보다 크다는 조건을 만족합니다.
풀이 접근 방법
핵심 아이디어는 알파벳을 거꾸로 나열한 기준 문자열("zyxwvutsrqponmlkjihgfedcba")을 활용하는 것입니다. 필요한 길이만큼 이 문자열에서 문자를 가져와 이어 붙이면, 별도의 비교 과정 없이도 조건을 자연스럽게 만족하는 결과를 얻을 수 있습니다.
알고리즘은 다음과 같이 진행됩니다.
- temp_str := 빈 문자열로 초기화
- extra := n mod 26 (마지막에 남는 불완전한 구간의 길이)
- extra가 1 이상이면:
· i를 26 − (extra + 1)부터 25까지 순회하며 temp_str에 str[i]를 추가
· count := n ÷ 26 (정수 나눗셈)
· i를 1부터 count + 1까지 반복하고, 각 회전마다 j를 0부터 25까지 순회하며 temp_str에 str[j]를 추가 - 완성된 temp_str 반환
동작 원리
extra는 전체 길이를 26으로 나눈 나머지로, 알파벳 한 바퀴(26자)로 정확히 나누어 떨어지지 않고 남는 부분을 의미합니다. 이 남은 부분은 역방향 알파벳의 끝쪽('a' 방향)에서 가져와 먼저 붙이고, 나머지 길이는 완전한 바퀴 단위로 채워 넣습니다.
참고로 알파벳 소문자는 총 26개뿐이므로, 엄격하게 감소하는 문자열은 최대 26글자까지 만들 수 있습니다. 따라서 이 문제는 일반적으로 n이 26 미만인 경우를 전제로 다룹니다.
Python 구현 예제
def show_string(n, str):
temp_str = ""
extra = n % 26
if (extra >= 1):
for i in range(26 - (extra + 1), 26):
temp_str += str[i]
count = n // 26
for i in range(1, count + 1):
for j in range(26):
temp_str += str[j]
return temp_str
n = 15
str = "zyxwvutsrqponmlkjihgfedcba"
print(show_string(n, str))
입력
15
출력
ponmlkjihgfedcba
복잡도 분석
결과 문자열의 길이가 n+1이므로, 시간 복잡도는 O(n)이며 공간 복잡도 역시 결과 저장을 위해 O(n)이 필요합니다.