문자열 s가 주어졌을 때, s의 문자들이 알파벳 순서(오름차순)로 배치되어 있는지 확인해야 합니다.
예를 들어 입력이 s = "mnnooop"이라면 출력은 True가 됩니다. 'm', 'n', 'n', 'o', 'o', 'o', 'p'의 각 문자가 이전 문자보다 크거나 같기 때문에 알파벳 순서를 유지하고 있다고 판단할 수 있습니다.
문제 해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다:
- 문자열 s의 문자들로 새 리스트 char_arr를 생성합니다.
- char_arr를 정렬합니다.
- 정렬된 char_arr가 원래 문자열의 문자 리스트와 동일하면 True, 그렇지 않으면 False를 반환합니다.
핵심 아이디어는 매우 직관적입니다. 문자열이 이미 알파벳 순서대로 되어 있다면, 그 문자들을 정렬해도 원래 순서가 그대로 유지됩니다. 따라서 정렬 전후의 결과를 비교하는 것만으로 조건 충족 여부를 판별할 수 있습니다.
예제 코드
def solve(s):
char_arr = list(s)
char_arr.sort()
return char_arr == list(s)
s = "mnnooop"
print(solve(s))
입력
"mnnooop"
출력
True
시간 복잡도 분석
위 풀이의 시간 복잡도는 O(n log n)입니다. 여기서 n은 문자열의 길이이며, 정렬 연산이 가장 큰 비용을 차지합니다. 공간 복잡도는 문자 리스트를 저장해야 하므로 O(n)입니다.
더 효율적인 대안: 인접 문자 비교
정렬 없이 인접한 문자 쌍만 비교하면 O(n)의 선형 시간에 문제를 해결할 수 있습니다:
def solve(s):
return all(s[i] <= s[i+1] for i in range(len(s)-1))
이 방법은 모든 인접한 문자 쌍이 앞의 문자가 뒤의 문자보다 작거나 같은지만 검사합니다. 하나라도 순서가 어긋나면 False를 반환하므로, 긴 문자열에서도 빠르게 결과를 얻을 수 있습니다.