문제 개요
문자열 S가 주어지고, 여기에 몇 가지 치환(replacement) 연산을 수행한다고 가정해 보겠습니다. 각 치환 연산은 세 가지 매개변수를 가집니다 — 시작 인덱스 i, 원본 단어(source) x, 대상 단어(target) y입니다. 규칙은 다음과 같습니다. 만약 x가 원본 문자열 S의 위치 i에서 시작한다면, 해당 위치에 등장하는 x를 y로 교체합니다. 조건이 맞지 않으면 아무 작업도 수행하지 않습니다.
예를 들어, S = "abcd"이고 치환 연산이 i = 2, x = "cd", y = "ffff"라고 해보겠습니다. "cd"가 원본 문자열 S의 2번 위치에서 시작하므로, 이 부분을 "ffff"로 교체해야 합니다.
또 다른 예를 살펴보겠습니다. S = "abcd"일 때, i = 0, x = "ab", y = "eee"인 치환 연산과 i = 2, x = "ec", y = "ffff"인 또 다른 치환 연산이 있다고 합시다. 두 번째 연산은 아무 효과가 없습니다. 원본 문자열에서 S[2] = 'c'인데, 이는 x[0] = 'e'와 일치하지 않기 때문입니다.
따라서 문자열 S = "abcd", 인덱스 배열 indexes = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]가 주어지면 최종 출력 결과는 "eeebffff"가 됩니다. 그 이유는 "a"가 S의 0번 위치에서 시작하므로 "eee"로 교체되고, "cd"는 S의 2번 인덱스에서 시작하므로 "ffff"로 교체되기 때문입니다.
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- (인덱스, 원래 순번) 쌍을 저장할 배열 sorted를 정의하고, n := 인덱스 배열의 크기로 설정합니다.
- i를 0부터 n-1까지 반복하면서 sorted에 (indexes[i], i) 쌍을 삽입합니다.
- sorted를 내림차순으로 정렬합니다. 뒤쪽 인덱스부터 처리하면 앞선 치환으로 인해 문자열 길이가 변하더라도 아직 처리하지 않은(더 앞쪽의) 인덱스에는 영향을 주지 않으므로 안전하게 교체할 수 있습니다.
- j를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- i := sorted[j] 쌍의 첫 번째 값
- src := sources[sorted[j] 쌍의 두 번째 값]
- target := targets[sorted[j] 쌍의 두 번째 값]
- 만약 S의 인덱스 i에서 시작하는 길이가 src 크기와 같은 부분 문자열이 src와 동일하다면, S := (S의 처음부터 i까지) + target + (S의 i + src.size()부터 끝까지)로 재구성합니다.
- 최종 문자열 S를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
vector < pair <int, int> > sorted;
int n = indexes.size();
for(int i = 0; i < n; i++){
sorted.push_back({indexes[i], i});
}
sort(sorted.rbegin(), sorted.rend());
for(int j = 0; j < n; j++){
int i = sorted[j].first;
string source = sources[sorted[j].second];
string target = targets[sorted[j].second];
if(S.substr(i, source.size()) == source){
S = S.substr(0, i) + target + S.substr(i + source.size());
}
}
return S;
}
};
main(){
vector<int> v1 = {0, 2};
vector<string> v2 = {"a", "cd"};
vector<string> v3 = {"eee", "ffff"};
Solution ob;
cout << (ob.findReplaceString("abcd", v1, v2, v3));
}입력
"abcd" [0, 2] ["a", "cd"] ["eee", "ffff"]
출력
eeebffff