문제 설명
소문자로 이루어진 목표(target) 문자열을 만들어야 한다고 가정해 보겠습니다.
처음 상태는 물음표('?')가 n개 나열된 시퀀스입니다(여기서 n은 목표 문자열의 길이입니다). 여기에 더해, 소문자로 구성된 하나의 스탬프(stamp)가 주어집니다.
매 턴마다 시퀀스 위에 스탬프를 찍어 해당 구간의 문자들을 스탬프의 문자로 교체할 수 있으며, 최대 10 × n턴까지 진행할 수 있습니다. 예를 들어 초기 시퀀스가 "?????"이고 스탬프가 "abc"라면, 첫 턴에 "abc??", "?abc?", "??abc"와 같은 문자열을 만들 수 있습니다.
목표 문자열을 만드는 것이 가능하다면, 각 턴에서 스탬프의 가장 왼쪽 문자가 찍힌 인덱스를 순서대로 담은 배열을 반환합니다. 만들 수 없다면 빈 배열을 반환하면 됩니다. 예를 들어 시퀀스가 "ababc"이고 스탬프가 "abc"라면 정답은 [0, 2]가 될 수 있습니다. "?????" → "abc??" → "ababc" 순서로 만들 수 있기 때문입니다.
따라서 입력이 stamp = "abcd", target = "abcdbcd"라면 출력은 [3, 0]이 됩니다.
풀이 전략
이 문제는 정방향으로 접근하기보다 목표 문자열에서 거꾸로 지워 나가는 방식이 효과적입니다. 스탬프와 일치하는 부분(또는 이미 '*'로 처리된 부분을 포함해 일치하는 부분)을 찾아 '*'로 덮어 나가고, 최종적으로 모든 문자가 '*'로 바뀌었다면 성공한 것으로 판단합니다. 구체적인 알고리즘 단계는 다음과 같습니다.
정답을 저장할 배열 ret을 정의합니다.
ok := true로 초기화합니다.
n := 스탬프의 길이, tsz := 0으로 설정합니다.
ok가 참인 동안 다음을 반복합니다.
ok := false로 두고, x := 0으로 초기화합니다.
sz를 스탬프 길이부터 1씩 감소시키며(sz > 0 동안), i를 0부터 (스탬프 길이 - sz)까지 증가시키면서 반복합니다.
newStamp := 길이 i의 '*' 문자열 + 스탬프의 i번째 문자부터 sz개의 부분 문자열 + 나머지 길이(스탬프 길이 - sz - i)만큼의 '*' 문자열로 구성합니다.
pos := target에서 newStamp가 등장하는 위치를 찾습니다.
pos가 target에 존재하는 동안 다음을 반복합니다.
ok := true로 갱신하고, x += sz를 누적합니다.
ret의 끝에 pos를 추가합니다.
target의 pos부터 pos + 스탬프 길이까지 '*'로 채웁니다.
pos := target에서 newStamp를 다시 검색합니다.
tsz += x를 누적합니다.
ret 배열을 뒤집습니다.
tsz가 target의 길이와 같으면 ret을, 그렇지 않으면 빈 배열을 반환합니다.
여기서 '*'는 '아무 문자와도 일치하는 와일드카드' 역할을 합니다. 스탬프의 일부만 사용하는 부분 일치(newStamp)를 활용하면, 가장자리가 잘린 스탬프 찍기도 역방향으로 되돌릴 수 있습니다. 더 나은 이해를 위해 아래 구현을 살펴보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
} cout << "]"<<endl;
}
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> ret;
bool ok = true;
int n = stamp.size();
int tsz = 0;
while (ok) {
ok = false;
int x = 0;
for (int sz = stamp.size(); sz > 0; sz--) {
for (int i = 0; i <= stamp.size() - sz; i++) {
string newStamp = string(i, '*') +
stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
int pos = target.find(newStamp);
while (pos != string::npos) {
ok = true;
x += sz;
ret.push_back(pos);
fill(target.begin() + pos, target.begin() +
pos + stamp.size(), '*');
pos = target.find(newStamp);
}
}
}
tsz += x;
}
reverse(ret.begin(), ret.end());
return tsz == target.size() ? ret : vector<int>();
}
};
main(){
Solution ob;
print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}입력
"abcd", "abcdbcd"
출력
[3, 0]
마무리
이 풀이의 핵심은 역방향 사고입니다. 스탬프를 찍어 문자열을 만드는 대신, 완성된 목표 문자열에서 스탬프 흔적을 하나씩 '*'로 지워 나가며 그 위치를 기록합니다. 모든 문자가 지워졌다면 기록된 위치를 뒤집은 순서가 곧 정답이 됩니다. 시간 복잡도는 대략 O(n² × m)(m은 스탬프 길이) 수준으로, n이 최대 1000인 제약 조건에서도 충분히 동작합니다.