길이가 n인 숫자 배열 A가 있다고 가정해 보겠습니다. 여기서 각 원소 A[i]는 문자열 s의 길이 (i + 1)짜리 접두사에 포함된 서로 다른 문자의 개수를 의미합니다. 우리의 목표는 이 접두사 배열 조건을 만족하는 문자열 중 사전순으로 가장 작은 문자열을 찾는 것입니다. 사용할 수 있는 문자는 영어 소문자 [a-z]로 제한되며, 조건을 만족하는 문자열이 존재하지 않으면 -1을 반환해야 합니다.
문제 이해하기
예를 들어 입력이 A = [1, 1, 2, 3, 4]라면 출력은 aabcd가 됩니다. prefix[0]에는 서로 다른 문자가 1개, prefix[1]에는 1개, prefix[2]에는 2개, prefix[3]에는 3개, prefix[4]에는 4개씩 포함되어 있고, 이 조건들을 모두 만족하는 문자열 중에서 해당 결과가 가장 사전순으로 앞서기 때문입니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- n := 배열 A의 크기로 설정합니다.
- character := 'a'로 초기화합니다.
- string := 빈 문자열로 초기화합니다.
- n이 1 미만이거나 A[0]이 1이 아니라면 -1을 반환합니다. 첫 번째 접두사에는 반드시 정확히 하나의 고유 문자만 존재해야 하기 때문입니다.
- string에 character를 이어 붙인 뒤, character를 다음 문자로 갱신합니다.
- i를 1부터 n - 1까지 반복하며 다음을 수행합니다:
- difference := A[i] - A[i - 1]을 계산합니다.
- difference가 1보다 크거나 0보다 작거나, A[i]가 26을 초과하면 -1을 반환합니다. 한 단계에서 새로운 문자는 최대 한 개까지만 추가될 수 있고, 소문자 알파벳은 총 26개뿐이기 때문입니다.
- difference가 0이라면 새로운 고유 문자가 등장하지 않은 것이므로 string에 'a'를 이어 붙입니다. 시작 문자가 항상 'a'이므로 이 선택은 안전하면서도 사전순으로 가장 작은 값입니다.
- 그 외의 경우(difference가 1)라면 새로운 고유 문자가 필요하다는 뜻이므로, string에 현재 character를 붙이고 character를 다음 문자로 갱신합니다.
- 모든 과정이 끝나면 완성된 string을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다:
def get_smallest_string(A):
n = len(A)
character = 'a'
string = ""
if (n < 1 or A[0] != 1):
return -1
string += str(character)
character = chr(ord(character) + 1)
for i in range(1, n):
difference = A[i] - A[i - 1]
if (difference > 1 or difference < 0 or A[i] > 26):
return -1
elif (difference == 0):
string += 'a'
else:
string += character
character = chr(ord(character) + 1)
return string
A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))입력
[1, 1, 2, 3, 4]출력
aabcd마무리
이 알고리즘은 배열을 단 한 번만 순회하므로 시간 복잡도는 O(n)이며, 공간 복잡도 역시 결과 문자열 저장에 비례하는 O(n)입니다. 핵심은 인접한 접두사 간의 고유 문자 개수 차이가 항상 0 또는 1이어야 하고, 전체 고유 문자 수가 26을 초과하지 않아야 한다는 점입니다. 이 두 가지 조건만 검증하면 선형 시간 안에 효율적으로 답을 구할 수 있습니다.