문제 이해하기
고대 우주비행사들이 사용하는 언어에는 일반적인 알파벳 순서와 다른 자신들만의 문자 배열 규칙이 있다고 상상해 봅시다. 우리에게는 이 특별한 규칙을 나타내는 문자열 사전이 하나 주어집니다. 이 사전은 고대 우주비행사 언어의 부분적인 사전식(lexicographic) 순서를 의미합니다.
우리의 과제는 임의의 문자열 s가 이 사전 순서에 따라 올바르게 정렬되어 있는지 확인하는 것입니다.
예시
예를 들어, 사전이 "bdc"이고 검사할 문자열이 "bbbb h ddd i cccc"라고 합시다. 이 경우 출력 결과는 True입니다. b는 d보다 먼저 등장하고, d는 c보다 먼저 등장하기 때문에 이 문자열은 주어진 사전 순서를 만족합니다.
해결 접근 방법
이 문제를 해결하려면 아래 단계를 따르면 됩니다.
사전(astro_dict)의 길이를 l에 저장합니다.
l이 0이라면, 즉 사전이 비어 있다면 True를 반환합니다. 정렬 기준이 없으므로 어떤 문자열이든 유효합니다.
인덱스 변수 i를 0으로 초기화합니다.
문자열 s의 각 문자 c에 대해 반복합니다.
c가 사전에 포함된 문자라면, i가 l보다 작고 astro_dict[i]가 c와 같지 않은 동안 i를 1씩 증가시킵니다.
이후 i가 l 이상이거나 astro_dict[i]가 c와 같지 않으면 False를 반환합니다. 이는 해당 문자가 사전 순서를 위반했음을 의미합니다.
모든 문자를 문제없이 통과하면 True를 반환합니다.
여기서 핵심은 인덱스 i가 한 번 증가하면 절대 되돌아가지 않는다는 점입니다. 덕분에 문자열 내에서 사전 순서가 거꾸로 흐르는 순간을 자연스럽게 감지할 수 있으며, 시간 복잡도는 문자열 길이 n과 사전 길이 m에 대해 O(n + m) 수준으로 매우 효율적입니다.
예제 코드
아래 구현 예시를 보면 더 쉽게 이해할 수 있습니다.
class Solution:
def solve(self, astro_dict, s):
l = len(astro_dict)
if l == 0:
return True
i = 0
for c in s:
if c in astro_dict:
while i < l and astro_dict[i] != c:
i += 1
if i >= l or astro_dict[i] != c:
return False
return True
ob = Solution()
print(ob.solve("bdc","bbbb h ddd i cccc"))
입력
"bdc","bbbb h ddd i cccc"
출력
True
마무리
이 알고리즘은 커스텀 사전 순서를 검증하는 전형적인 패턴을 보여줍니다. 단일 포인터를 활용해 사전 위치를 추적함으로써 불필요한 반복을 줄이고 선형 시간 안에 결과를 얻을 수 있습니다. 외래어 사전 정렬, 사용자 지정 알파벳 검증 등 실제 프로젝트에서도 유용하게 응용할 수 있는 개념이니 꼭 기억해 두시길 바랍니다.