문제 개요
소문자 'x'와 'y'로만 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 한 번의 연산으로 문자 하나를 골라 'x'를 'y'로 바꾸거나, 반대로 'y'를 'x'로 바꿀 수 있습니다. 이때 문자열 안의 모든 'x'가 모든 'y'보다 앞쪽에 오도록 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다.
예를 들어 입력이 s = "yxyyyyxyxx"라면, 출력은 4가 됩니다.
접근 방법
핵심 아이디어는 문자열을 왼쪽에서 오른쪽으로 한 번만 훑으면서, 각 위치를 분할 지점으로 삼는 것입니다. 어떤 지점을 기준으로 할 때 비용은 다음과 같이 정의됩니다.
y_left: 현재 지점보다 앞쪽에 있는 'y'의 개수 (앞쪽 구간이 올바르려면 'x'로 바꿔야 함)
x_right: 현재 지점부터 뒤쪽에 남아 있는 'x'의 개수 (뒤쪽 구간이 올바르려면 'y'로 바꿔야 함)
각 지점에서 y_left + x_right를 계산하고, 그중 최솟값을 답으로 선택하면 됩니다.
알고리즘 단계
y_left := 0으로 초기화합니다.
x_right와 res를 문자열 내 'x'의 총 개수로 초기화합니다.
문자열의 각 문자를 순회하며 다음을 수행합니다.
문자가 'x'이면 x_right를 1 감소시킵니다.
그렇지 않으면('y'이면) y_left를 1 증가시킵니다.
res를 res와 (y_left + x_right) 중 작은 값으로 갱신합니다.
순회가 끝나면 res를 반환합니다.
이 방법은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)로 매우 효율적입니다.
구현 예제
class Solution:
def solve(self, s):
y_left = 0
x_right = res = s.count("x")
for item in s:
if item == "x":
x_right -= 1
else:
y_left += 1
res = min(res, y_left + x_right)
return res
ob = Solution()
s = "yxyyyyxyxx"
print(ob.solve(s))
입력
"yxyyyyxyxx"
출력
4
동작 원리 살펴보기
입력 "yxyyyyxyxx"의 경우, 처음에는 전체 'x'의 개수인 4로 시작합니다. 문자를 하나씩 이동하면서 분할 지점 앞의 'y' 개수와 뒤의 'x' 개수 합을 계속 갱신하면, 특정 지점에서 최솟값 4를 얻게 됩니다. 이는 네 번의 문자 변경만으로 모든 'x'를 모든 'y' 앞에 배치할 수 있음을 의미합니다.