문제 개요
두 개의 문자열 s와 t가 주어졌을 때, 특정 조건 하에서 한 문자열을 다른 문자열로 변환할 수 있는지 확인하는 문제입니다. 변환 규칙은 다음과 같습니다.
- 이미 모음인 문자는 반드시 다른 모음으로만 변경할 수 있습니다.
- 이미 자음인 문자는 반드시 다른 자음으로만 변경할 수 있습니다.
즉, 모음을 자음으로 바꾸거나 자음을 모음으로 바꾸는 것은 허용되지 않습니다. 이러한 규칙 안에서 s를 t로 변환할 수 있는지(혹은 그 반대도 동일하게 적용됨) 판별해야 합니다.
예시
예를 들어 s = "udpmva", t = "itmmve"라고 가정해 보겠습니다. 이 경우 출력은 True가 됩니다. 각 위치의 문자가 같은 종류(모음 또는 자음)끼리 대응되기 때문입니다.
- u → i (모음 → 모음)
- d → t (자음 → 자음)
- p → m (자음 → 자음)
- a → e (모음 → 모음)
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 문자열 s의 길이(s_size)를 구합니다.
- s와 t의 길이가 다르면 변환이 불가능하므로 False를 반환합니다.
- 0부터 s_size까지 반복하면서 각 위치의 문자를 비교합니다.
- s[i]와 t[i]가 둘 다 모음이면 → 다음 반복으로 진행합니다.
- s[i]와 t[i]가 둘 다 모음이 아니면(자음) → 다음 반복으로 진행합니다.
- 그 외의 경우(하나는 모음, 하나는 자음) → False를 반환합니다.
- 모든 위치를 통과했다면 True를 반환합니다.
핵심 아이디어는 간단합니다. 각 인덱스에서 두 문자의 '종류'만 일치하면 되고, 실제 어떤 문자인지는 중요하지 않습니다. 왜냐하면 같은 종류 내에서는 어떤 문자든 자유롭게 바꿀 수 있기 때문입니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def isVowel(x):
if x in ['a', 'e', 'i', 'o', 'u']:
return True
return False
def solve(s, t):
s_size = len(s)
if (s_size != len(t)):
return False
for i in range(s_size):
if (isVowel(s[i]) and isVowel(t[i])):
continue
elif ((isVowel(s[i])) == False and (isVowel(t[i]) == False)):
continue
else:
return False
return True
s, t = "udpgma", "itmmve"
print(solve(s, t))입력
"udpgma", "itmmve"
출력
True
코드 설명
isVowel() 함수는 전달받은 문자가 모음(a, e, i, o, u)에 포함되어 있는지 확인하여 불리언 값을 반환하는 헬퍼 함수입니다.
solve() 함수는 먼저 두 문자열의 길이가 같은지 검사하고, 이후 각 인덱스를 순회하며 두 문자가 동일한 종류(모음-모음 또는 자음-자음)인지 확인합니다. 하나라도 종류가 어긋나는 위치가 있다면 즉시 False를 반환하고, 끝까지 문제없이 통과하면 True를 반환합니다.
복잡도 분석
- 시간 복잡도: O(n) — 문자열의 길이 n만큼 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 상수 공간만 사용합니다.
참고로 위 예제에서 입력 문자열이 "udpgma"로 표기되어 있지만, 설명 부분의 예시("udpmva")와 마찬가지로 각 위치의 문자 종류가 서로 일치하기 때문에 결과는 True로 출력됩니다.