문제 설명
소문자로만 이루어진 두 문자열 s와 t가 있다고 가정해 보겠습니다. 한 번의 연산으로 s 또는 t의 임의의 문자를 다른 소문자 알파벳으로 바꿀 수 있으며, 다음 세 조건 중 하나를 반드시 만족해야 합니다.
- s의 모든 문자가 알파벳 순서에서 t의 모든 문자보다 엄격하게 앞서 있어야 합니다.
- t의 모든 문자가 알파벳 순서에서 s의 모든 문자보다 엄격하게 앞서 있어야 합니다.
- s와 t가 모두 단 하나의 동일한 문자로만 이루어져야 합니다.
목표는 세 조건 중 하나를 달성하기 위해 필요한 최소 연산 횟수를 구하는 것입니다.
예제로 이해하기
예를 들어 s = "sts", t = "uss"가 입력으로 주어지면 출력은 2입니다. 그 이유는 다음과 같습니다.
- t를 두 번의 연산으로 "uuu"로 바꾸면, s의 모든 문자가 t의 모든 문자보다 작아집니다.
- s를 "ttt"로, t를 "sss"로 바꾸면(세 번의 연산), t의 모든 문자가 s의 모든 문자보다 작아집니다.
- s와 t를 각각 "sss"로 바꾸면(두 번의 연산), 두 문자열이 모두 하나의 문자로만 구성됩니다.
즉, 첫 번째 또는 세 번째 방법처럼 두 번의 연산만으로 조건을 충족할 수 있으며, 이것이 최솟값입니다.
풀이 접근 방법
알파벳 소문자 각각을 기준점으로 삼아 세 가지 경우의 비용을 계산한 뒤, 그중 가장 작은 값을 선택하면 됩니다.
- unique: 두 문자열 전체를 같은 문자 c 하나로 통일하는 비용 → len(s) + len(t) - counter_s[c] - counter_t[c]
- less_s: s의 모든 문자를 c보다 작게, t의 모든 문자를 c 이상으로 만드는 비용
- less_t: t의 모든 문자를 c보다 작게, s의 모든 문자를 c 이상으로 만드는 비용
여기서 accu_s와 accu_t는 지금까지 살펴본 문자(c보다 앞선 문자)의 누적 등장 횟수를 의미합니다. 알파벳을 순서대로 순회하며 누적합을 갱신하면 각 경계 지점의 비용을 상수 시간에 구할 수 있습니다.
알고리즘 단계
- counter_s := s의 문자별 빈도수를 저장하는 맵
- counter_t := t의 문자별 빈도수를 저장하는 맵
- less_s, less_t, unique := 무한대로 초기화
- accu_s, accu_t := 0으로 초기화
- 소문자 알파벳의 각 문자 c에 대해:
- unique := min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
- c가 'a'보다 크면:
- less_s := min(less_s, len(s) - accu_s + accu_t)
- less_t := min(less_t, len(t) - accu_t + accu_s)
- accu_s := accu_s + counter_s[c]
- accu_t := accu_t + counter_t[c]
- min(less_s, less_t, unique) 반환
Python 구현 예제
다음 코드로 직접 확인해 보겠습니다.
from collections import Counter
import string
def solve(s, t):
counter_s = Counter(s)
counter_t = Counter(t)
less_s, less_t, unique = float('inf'), float('inf'), float('inf')
accu_s, accu_t = 0, 0
for c in string.ascii_lowercase:
unique = min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
if c > 'a':
less_s = min(less_s, len(s) - accu_s + accu_t)
less_t = min(less_t, len(t) - accu_t + accu_s)
accu_s += counter_s[c]
accu_t += counter_t[c]
return min(less_s, less_t, unique)
s = 'sts'
t = 'uss'
print(solve(s, t))
참고로 원본 코드에는 조건 1, 2의 계산 결과를 less_a, less_b에 저장해 최종 답에 반영되지 않는 실수가 있었는데, 여기서는 less_s, less_t로 바로잡아 올바른 결과가 나오도록 수정했습니다.
입력 및 실행 결과
입력:
'sts', 'uss'
출력:
2
복잡도 분석
두 문자열 길이의 합을 n이라 할 때 시간 복잡도는 O(n + 26), 즉 O(n)입니다. 빈도 카운터는 알파벳 26개로 고정되어 있으므로 추가 공간 복잡도는 O(1)입니다.