문제 개요
소문자로 구성된 목표 문자열을 만들려고 한다고 가정해 봅시다. 처음에는 목표 문자열의 길이 n만큼 물음표('?')로 이루어진 시퀀스가 주어지며, 소문자로 이루어진 하나의 스탬프(stamp)를 사용할 수 있습니다. 각 턴마다 스탬프를 시퀀스 위에 놓아 해당 위치의 문자들을 스탬프의 문자로 덮어쓸 수 있으며, 최대 10 × n턴까지 진행할 수 있습니다.
예를 들어 초기 시퀀스가 "?????"이고 스탬프가 "abc"라면, 첫 턴에 "abc??", "?abc?", "??abc" 같은 문자열을 만들 수 있습니다. 목표 문자열을 만드는 것이 가능하다면 각 턴에 스탬프를 찍은 가장 왼쪽 문자의 인덱스를 순서대로 담은 배열을 반환하고, 불가능하다면 빈 배열을 반환합니다. 예컨대 시퀀스가 "ababc"이고 스탬프가 "abc"라면 정답은 [0, 2]입니다. "?????" → "abc??" → "ababc" 순서로 만들 수 있기 때문입니다.
따라서 입력이 s = "abcd", t = "abcdbcd"일 때 출력은 [3, 0]이 됩니다.
접근 방법
이 문제는 스탬프를 앞으로 찍는 대신, 목표 문자열에서 스탬프 패턴을 찾아 물음표로 되돌리는 역방향 그리디 방식으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- s의 길이가 1이라면, t의 모든 문자가 s[0]과 일치할 때 [0, 1, ..., len(t)-1]을 반환하고, 그렇지 않으면 빈 리스트를 반환합니다.
- 정답을 저장할 빈 리스트 ans를 준비합니다.
- t가 전부 '?'가 될 때까지 다음 과정을 반복합니다.
- 변화 여부를 확인하기 위해 현재 t를 tmp에 저장해 둡니다.
- i를 0부터 len(s)-1까지, j를 len(s)부터 i+1까지 역순으로 순회하며 탐색 패턴을 만듭니다: '?' × i + s[i:j] + '?' × (len(s) − j)
- 이 패턴이 t에 존재하는 동안, 해당 시작 인덱스를 ans에 추가하고 그 부분을 '?' × len(s)로 한 번씩 교체합니다.
- t가 모두 '?'가 되면 내부 반복을 종료합니다.
- 한 바퀴를 돌 동안 t에 아무 변화가 없다면(tmp == t) 더 이상 진행할 수 없으므로 빈 배열을 반환합니다.
- 모든 처리가 끝나면 ans를 뒤집어 반환합니다. 역방향으로 기록했기 때문에 실제 스탬핑 순서는 반대가 되기 때문입니다.
구현 예시
다음 파이썬 코드를 통해 위 알고리즘을 더 잘 이해할 수 있습니다.
def solve(s, t): if len(s) == 1: return [i for i in range(len(t))] if all(c == s[0] for c in t) else [] ans = [] while t != "?" * len(t): tmp = t for i in range(len(s)): for j in reversed(range(i+1, len(s)+1)): search = "?" * i + s[i:j] + "?" * (len(s)-j) while t.find(search) != -1: ans.append(t.find(search)) t = t.replace(search, "?"*len(s), 1) if t == "?" * len(t): break if t == "?" * len(t): break if tmp == t: return [] return ans[::-1] s = "abcd" t = "abcdbcd" print(solve(s, t))
동작 원리
정방향으로 스탬프를 찍으면 나중에 찍은 스탬프가 앞서 찍은 것을 덮어쓸 수 있어 순서를 추적하기 어렵습니다. 반면 목표 문자열에서 스탬프와 일치하는 부분(물음표 포함)을 찾아 물음표로 되돌리면, 가장 마지막에 찍힌 스탬프부터 차례로 확정됩니다. 따라서 역방향으로 기록한 인덱스 배열을 뒤집으면 정방향 스탬핑 순서를 얻을 수 있습니다.
입력
"abcd", "abcdbcd"
출력
[3,0]