문제 개요
소문자로 이루어진 두 문자열 s와 t가 주어졌을 때, 다음과 같은 제약 조건을 만족하며 s로부터 t를 생성할 수 있는지 확인해야 합니다.
- t의 각 문자는 s에 존재해야 합니다. 예를 들어 t에 'a'가 두 개 있다면, s에도 정확히 두 개의 'a'가 있어야 합니다.
- t의 어떤 문자가 s에 없다면, 해당 문자보다 ASCII 값이 하나 및 둘 앞선 두 문자가 s에 있는지 확인합니다. 예를 들어 'f'가 t에는 있지만 s에는 없다면, s의 'd'와 'e'를 조합하여 'f'를 대신 만들 수 있습니다.
예를 들어 입력이 s = "pghn", t = "pin"이라면 결과는 True입니다. 'i'를 'g'와 'h'로 만들 수 있기 때문에 "pin"을 완성할 수 있습니다.
해결 접근 방식
이 문제는 빈도 카운팅(frequency counting) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘은 다음 단계로 진행됩니다.
- s에 포함된 각 문자의 등장 횟수를 저장하는 freq 딕셔너리를 생성합니다.
- t의 각 문자를 순서대로 확인합니다.
- freq[t[i]] 값이 0이 아니라면(즉, 해당 문자가 아직 남아 있다면) 그 값을 1 감소시킵니다.
- 그렇지 않고, t[i] 바로 앞 두 문자(ASCII 값 기준)가 모두 freq에 남아 있다면 두 문자의 값을 각각 1씩 감소시킵니다.
- 위 조건 중 어느 것도 만족하지 않으면 False를 반환합니다.
- 모든 문자를 처리했다면 True를 반환합니다.
구현 코드
from collections import defaultdict
def solve(s, t):
freq = defaultdict(lambda:0)
for i in range(0, len(s)):
freq[s[i]] += 1
for i in range(0, len(t)):
if freq[t[i]]:
freq[t[i]] -= 1
elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]):
freq[chr(ord(t[i]) - 1)] -= 1
freq[chr(ord(t[i]) - 2)] -= 1
else:
return False
return True
s = "pghn"
t = "pin"
print(solve(s, t))
입력
"pghn", "pin"
출력
True
코드 설명
먼저 defaultdict를 사용해 s의 모든 문자 빈도를 계산합니다. 이후 t의 문자를 순회하면서 세 가지 경우를 검사합니다. 첫 번째는 해당 문자가 s에 남아 있는 경우이고, 두 번째는 앞선 두 ASCII 문자를 조합해 대체할 수 있는 경우입니다. 마지막으로 어느 조건도 충족되지 않으면 즉시 False를 반환하여 불필요한 연산을 줄입니다.
이 알고리즘의 시간 복잡도는 O(len(s) + len(t))이며, 공간 복잡도는 O(1)입니다. 알파벳 소문자만 다루므로 빈도 딕셔너리의 크기는 최대 26으로 고정되기 때문입니다.