문제 설명
길이가 짝수인 소문자 문자열 s가 주어졌다고 가정해 보겠습니다. 우리는 모든 i(0 ≤ i < n/2)와 j(n/2 ≤ j < n)에 대해 아래 세 가지 조건 중 하나가 성립하도록 문자열을 변경할 때, 변경해야 할 문자의 최소 개수를 구해야 합니다.
- s[i] > s[j]
- s[i] < s[j]
- s[i] == s[j]
예를 들어 입력이 s = "pppxxp"라고 한다면 출력은 1입니다. 마지막 'p'를 'x'로 바꿔주면 s[i] < s[j] 조건을 충족할 수 있기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n := 문자열 s의 길이
- left := s의 왼쪽 절반에 등장하는 각 문자의 빈도수를 저장한 딕셔너리
- right := s의 오른쪽 절반에 등장하는 각 문자의 빈도수를 저장한 딕셔너리
- ans := n
- 영문 소문자의 각 문자 pivot에 대해 다음을 수행합니다.
- ans := ans와 (n − left[pivot] − right[pivot]) 중 더 작은 값
- good := left에서 c ≤ pivot인 모든 c에 대한 left[c] 값의 합
- good := good + right에서 c > pivot인 모든 c에 대한 right[c] 값의 합
- ans := ans와 (n − good) 중 더 작은 값
- good := left에서 c > pivot인 모든 c에 대한 left[c] 값의 합
- good := good + right에서 c ≤ pivot인 모든 c에 대한 right[c] 값의 합
- ans := ans와 (n − good) 중 더 작은 값
- ans 반환
알고리즘 동작 원리
세 가지 조건이 알고리즘과 어떻게 대응되는지 살펴보면 다음과 같습니다.
- s[i] == s[j]인 경우: 문자열 전체가 하나의 문자로만 이루어져야 하므로, 가장 빈도가 높은 문자를 남기고 나머지를 모두 변경합니다.
- s[i] < s[j]인 경우: 왼쪽 절반의 모든 문자가 오른쪽 절반의 모든 문자보다 작아야 합니다. 기준 문자(pivot)를 정해 왼쪽에서는 pivot 이하의 문자를, 오른쪽에서는 pivot 초과의 문자만 그대로 두고 나머지는 변경합니다.
- s[i] > s[j]인 경우: 위와 반대로 왼쪽에는 pivot 초과의 문자를, 오른쪽에는 pivot 이하의 문자를 유지합니다.
모든 가능한 pivot에 대해 필요한 변경 횟수를 계산한 뒤 그중 최솟값을 선택하면 정답을 얻을 수 있습니다.
예제
아래 구현을 통해 더 자세히 이해해 봅시다.
from collections import Counter
from string import ascii_lowercase
def solve(s):
n = len(s)
left = Counter(s[: n >> 1])
right = Counter(s[n >> 1 :])
ans = n
for pivot in ascii_lowercase:
ans = min(ans, n - left[pivot] - right[pivot])
good = sum(left[c] for c in left if c <= pivot)
good += sum(right[c] for c in right if c > pivot)
ans = min(ans, n - good)
good = sum(left[c] for c in left if c > pivot)
good += sum(right[c] for c in right if c <= pivot)
ans = min(ans, n - good)
return ans
s = "pppxxp"
print(solve(s))
입력
"pppxxp"
출력
1