문제 개요
길이가 같은 두 문자열 s1과 s2가 주어졌을 때, s1의 어떤 순열(permutation)이 s2의 어떤 순열을 깨뜨릴 수 있는지, 혹은 그 반대가 가능한지 확인해야 합니다.
여기서 문자열 a가 문자열 b를 "깨뜨린다"는 것은, 인덱스 0부터 n-1까지의 모든 i에 대해 x[i] >= y[i](알파벳 순서 기준)를 만족한다는 의미입니다.
예를 들어 입력이 s1 = "abc", s2 = "xya"라고 가정해 보겠습니다. 이 경우 출력은 true가 됩니다. s2의 순열인 "ayx"가 s1의 순열인 "abc"를 깨뜨릴 수 있기 때문입니다. 실제로 각 위치를 비교하면 'a' >= 'a', 'y' >= 'b', 'x' >= 'c'로 모든 조건을 충족합니다.
해결 접근 방법
이 문제의 핵심 아이디어는 두 문자열을 모두 알파벳 순으로 정렬한 뒤, 같은 위치의 문자들을 하나씩 비교하는 것입니다. 정렬된 상태에서 한쪽이 다른 쪽의 모든 위치에서 크거나 같다면, 해당 순열 조합이 성립함을 보장할 수 있습니다.
먼저 check() 함수를 정의합니다. 이 함수는 두 문자열 s1과 s2를 받아 s1이 s2를 깨뜨릴 수 있는지 검사하며, 다음과 같이 동작합니다.
- i를 0으로 초기화하고, i가 s1의 길이보다 작을 동안 i를 1씩 증가시키며 반복합니다.
- 반복 과정에서 s2[i] < s1[i]인 지점이 발견되면 false를 반환합니다.
- 모든 위치를 통과하면 true를 반환합니다.
메인 메소드에서는 다음 작업을 수행합니다.
- s1을 오름차순으로 정렬합니다.
- s2를 오름차순으로 정렬합니다.
- f3 = check(s2, s1)로 s2가 s1을 깨뜨릴 수 있는지 확인합니다.
- f4 = check(s1, s2)로 s1이 s2를 깨뜨릴 수 있는지 확인합니다.
- f3 또는 f4 중 하나라도 true이면 true를 반환하고, 둘 다 아니면 false를 반환합니다.
예제 코드
아래 C++ 구현 예시를 통해 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool check(string& s1, string& s2){
for (int i = 0; i < s1.size(); i++) {
if (s2[i] < s1[i])
return false;
}
return true;
}
bool checkIfCanBreak(string s1, string s2) {
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
bool f3 = check(s2, s1);
bool f4 = check(s1, s2);
return f3 || f4;
}
};
main(){
Solution ob;
cout << (ob.checkIfCanBreak("abc", "xya"));
}입력 및 출력 결과
입력:
"abc", "xya"
출력:
1
복잡도 분석
시간 복잡도: 두 문자열을 각각 정렬하는 데 O(n log n)이 소요되고, 이후 위치별 비교에는 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도: 제자리 정렬을 활용하므로 추가 공간은 O(1) 수준입니다(정렬 알고리즘 내부 스택은 제외).