원제: Minimum Operations to Sort a String
| 플랫폼 | 문제 번호 | 난이도 | 언어 |
|---|---|---|---|
| 리트코드 | 3863 | 보통 (Medium) | Python 3 |
문자열에서 전체 문자열이 아닌 부분 문자열 하나를 골라 오름차순으로 정렬하는 연산을 반복할 때, 전체 문자열을 정렬하는 최소 연산 횟수를 반환한다. 주어진 부분 문자열은 연속한 구간이며, 정렬할 구간으로 문자열 전체를 선택할 수 없다.
s는 소문자 영어 알파벳으로만 이루어지고, 1 <= s.length <= 10^5이다. 이미 정렬되어 있으면 0을 반환하고, 조건을 지키며 정렬할 수 없으면 -1을 반환한다.
예제 1: s = "dog" → 1. 부분 문자열 "og"를 정렬하면 "dgo"가 된다. 예제 2: s = "card" → 2. "car"를 정렬해 "acrd"로 만든 뒤, "rd"를 정렬해 "acdr"로 만든다. 예제 3: s = "gf" → -1. 길이 2인 문자열 전체를 정렬하지 않고는 순서를 바꿀 수 없다.
코드는 먼저 이미 정렬된 경우를 제외하고, 길이 2인 문자열은 정렬되지 않았다면 -1로 처리한다. 그 외에는 문자열의 최솟값과 최댓값이 양 끝에 놓였는지 살핀다. 첫 문자가 최솟값이면 첫 문자를 고정하고 나머지 접미사를 정렬해 전체를 정렬할 수 있고, 마지막 문자가 최댓값인 경우도 대칭적으로 한 번이면 된다.
두 끝 조건이 모두 성립하지 않으면 보통 두 번으로 정렬할 수 있다. 다만 첫 문자가 유일한 최댓값이고 마지막 문자가 유일한 최솟값인 경우에는 두 끝을 한 번의 부분 문자열 정렬로 함께 바로잡을 수 없다. 코드가 이 경우에만 3을 반환하는 것은 두 끝의 위치를 정리하는 데 추가 단계가 필요하기 때문이다.
코드는 다음 순서로 조건을 검사한다.
"".join(sorted(s)) == s이면 이미 비내림차순이므로 0을 반환한다. sorted(s)는 문자를 정렬한 목록이고, join으로 문자열로 바꿔 원본과 비교한다.smallest = min(s), largest = max(s)를 구한다. s[0] == smallest or s[-1] == largest이면 1을 반환한다. 해당 끝 문자를 그대로 두고 나머지 부분 문자열을 정렬하면 전체가 정렬된다.s[0] == largest and s[-1] == smallest이면서 양 극값이 각각 한 번만 나타나면 3을 반환한다. s.count(...) == 1 조건은 최댓값과 최솟값이 실제로 양 끝에만 있는 특수한 배치를 가려낸다. 이외의 경우는 2를 반환한다.class Solution:
def minOperations(self, s: str) -> int:
if "".join(sorted(s)) == s:
return 0
if len(s) == 2:
return -1
smallest = min(s)
largest = max(s)
if s[0] == smallest or s[-1] == largest:
return 1
if (s[0] == largest and s[-1] == smallest and s.count(largest) == 1 and s.count(smallest) == 1):
return 3
return 2
n = len(s)라 하면 sorted(s)가 O(n log n) 시간과 O(n) 공간을 사용한다. 이후 min, max, count는 각각 O(n)이고, 조건문은 상수 개이므로 전체 시간 복잡도는 O(n log n), 보조 공간은 정렬 목록에 필요한 O(n)이다. 추가 결과를 저장하는 공간은 반환할 정수 하나뿐이다.
부분 문자열은 전체 문자열을 제외해야 하므로, 정렬되지 않은 길이 2 문자열은 불가능하다. 코드의 3회 분기는 끝 문자가 유일한 최댓값·최솟값인 경우에만 적용된다. 양 끝 문자의 조건은 우선순위대로 검사하므로, 한 번이면 되는 경우가 특수 분기보다 먼저 반환된다.