문제 개요
같은 길이를 가진 두 문자열 s와 t가 주어졌을 때, s의 어떤 순열 s1과 t의 어떤 순열 t1이 다음 조건 중 하나를 만족하는지 확인해야 합니다.
- 모든 인덱스 i(0 ≤ i < n)에 대해 s1[i] ≤ t1[i]
- 또는 모든 인덱스 i(0 ≤ i < n)에 대해 t1[i] ≤ s1[i]
예를 들어 입력이 s = "vyx", t = "wzx"라면 결과는 True입니다. s1 = "vxy", t1 = "wxz"로 재배열하면 모든 위치에서 s1[i] ≤ t1[i]가 성립하기 때문입니다.
해결 접근 방법
이 문제는 정렬을 활용하면 간단하게 해결할 수 있습니다. 두 문자열을 각각 오름차순으로 정렬한 뒤, 한쪽이 다른 쪽보다 모든 위치에서 작거나 같은지만 검사하면 됩니다. 정렬된 상태에서 이 조건이 성립하지 않는다면, 어떤 순열로도 조건을 만족시킬 수 없습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- s와 t가 빈 문자열이면 True를 반환합니다.
- 문자열 s와 t를 각각 정렬합니다.
- util() 함수를 정의합니다. 이 함수는 s1과 t1을 받아 s1의 모든 문자가 t1의 같은 위치 문자보다 작거나 같은지 확인하고, 하나라도 크면 False를 반환합니다.
- 메인 로직에서 util(s, t)가 참이면 True를 반환합니다.
- 그렇지 않으면 s와 t의 순서를 서로 바꾼 뒤 util(s, t)를 다시 호출하여 그 결과를 반환합니다.
예제 코드
class Solution:
def solve(self, s, t):
if not len(s) or not len(t):
return True
s = sorted(s)
t = sorted(t)
def util(s1, t1):
for i in range(len(s1)):
if s1[i] > t1[i]:
return False
return True
if util(s, t):
return True
s, t = t, s
return util(s, t)
ob = Solution()
s = "vyx"
t = "wzx"
print(ob.solve(s, t))
입력
"vyx", "wzx"
출력
True
복잡도 분석
두 문자열의 정렬에 O(n log n)의 시간이 소요되고, 이후 요소별 비교에는 O(n)이 필요하므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 정렬된 문자 리스트를 저장하기 위해 O(n)입니다.