Python으로 두 문자열 사이에 있는 사전순 문자열 찾는 방법

두 문자열 S와 T가 주어졌을 때, 길이가 같으면서 사전순(lexicographically)으로 S보다 크고 T보다 작은 문자열이 존재하는지 확인해야 합니다. 만약 그러한 문자열이 없다면 -1을 반환합니다.

여기서 말하는 사전순 비교는 다음과 같이 정의됩니다. S = S1S2…Sn이 T = T1T2…Tn보다 사전순으로 작다는 것은, 어떤 인덱스 i가 존재하여 S1 = T1, S2 = T2, …, Si−1 = Ti−1을 만족하면서 Si < Ti인 경우를 의미합니다.

예를 들어 입력이 S = "bbb", T = "ddd"라면 출력은 "bbc"가 됩니다. "bbc"는 "bbb"보다 크고 "ddd"보다 작으며, 길이도 3으로 동일하기 때문입니다.

접근 방법

핵심 아이디어는 숫자를 1만큼 증가시키는 것과 같습니다. 문자열을 뒤에서부터 앞으로 탐색하며 가장 마지막 자리의 문자를 하나씩 올려보는 것인데, 이는 사전순으로 바로 다음에 오는 문자열을 구하는 문제와 본질적으로 동일합니다. 해결 절차는 다음과 같습니다.

• n := 문자열의 길이
• i를 n − 1부터 0까지 1씩 감소시키며 반복:
  • string[i]가 'z'가 아니라면:
    • k := string[i]의 ASCII 값
    • string[i] := ASCII 코드가 k + 1인 문자
    • 문자들을 이어 붙여 결과를 반환
  • string[i]가 'z'라면 string[i] := 'a'로 바꾸고 한 자리 앞으로 이동 (올림 처리)

'z'를 만나면 'a'로 되돌리고 앞 자리로 넘어가는 과정은 마치 숫자 계산에서 9가 0으로 넘어갈 때 받아올림(carry)이 발생하는 원리와 같습니다. 모든 문자가 'z'라면 더 이상 조건을 만족하는 문자열이 없으므로 -1을 반환하면 됩니다.

구현 예제

다음 파이썬 코드로 위 알고리즘을 확인해 보겠습니다.

def find_next(string):
    n = len(string)
    for i in range(n - 1, -1, -1):
        if string[i] != 'z':
            k = ord(string[i])
            string[i] = chr(k + 1)
            return ''.join(string)
        string[i] = 'a'

S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)

if res != T:
    print(res)
else:
    print(-1)

입력

"bbb", "ddd"

출력

bbc

동작 과정 살펴보기

S = "bbb"인 경우를 단계별로 살펴보겠습니다. 먼저 마지막 문자 'b'를 검사합니다. 'z'가 아니므로 한 글자 올려 'c'로 바꾸고 즉시 "bbc"를 반환합니다. 반환된 "bbc"는 T인 "ddd"와 같지 않으므로 그대로 출력되며, S보다 크고 T보다 작다는 조건을 모두 만족합니다.

주의할 점도 있습니다. S = "zzz"처럼 모든 문자가 'z'라면 함수가 None을 반환하게 되는데, 실제 구현에서는 이 경우를 명시적으로 처리해 -1을 출력하도록 하는 것이 안전합니다. 또한 결과가 T와 정확히 일치하면 T 미만이라는 조건을 벗어나므로 역시 -1을 출력해야 합니다. 이런 경계 조건까지 고려하면 더 견고한 코드를 작성할 수 있습니다.