문자열 문제에서는 공백이나 구분자가 사라진 문자열을 의미 있는 조각들로 다시 나누는 문제가 자주 나옵니다.
겉보기에는 앞에서부터 잘라 보면 될 것 같지만, 가능한 잘라내기 경우가 많아지면 같은 위치를 여러 번 다시 확인하게 됩니다.
이번 글에서는 공백 없이 이어진 명령 문자열을 사전에 있는 토큰들로 복원할 수 있는지 확인하는 방법을 정리해보겠습니다.
문제
명령어 조각 목록과 구분자가 없는 문자열이 주어집니다.
문자열을 조각 목록에 있는 항목들로 나눌 수 있다면, 그 결과를 배열로 반환하세요.
가능한 나누기 방법이 여러 개라면 그중 하나만 반환하면 됩니다.
나눌 수 없다면 null을 반환하세요.
예시 1
tokens = ["build", "cache", "clear", "deploy"]
stream = "buildcacheclear"
이 문자열은 다음처럼 복원할 수 있습니다.
"build" + "cache" + "clear"
따라서 결과는 다음과 같습니다.
["build", "cache", "clear"]
예시 2
tokens = ["fast", "api", "fastapi", "docs"]
stream = "fastapidocs"
이 경우 가능한 복원은 두 가지입니다.
"fast" + "api" + "docs"
"fastapi" + "docs"
둘 중 어느 결과를 반환해도 괜찮습니다.
예시 3
tokens = ["spring", "boot", "java"]
stream = "springcloud"
cloud라는 토큰이 목록에 없기 때문에 전체를 복원할 수 없습니다.
따라서 결과는 다음과 같습니다.
null
처음 떠오르는 생각
문자열 앞에서부터 가능한 토큰을 하나씩 잘라보면 됩니다.
예를 들어 buildcacheclear가 있으면:
b
bu
bui
build
처럼 점점 늘려 가며 확인할 수 있습니다.
build가 사전에 있다면,
남은 문자열 cacheclear를 다시 같은 방식으로 확인하면 됩니다.
이 구조는 재귀로 자연스럽게 풀 수 있습니다.
하지만 단순 재귀만 쓰면 같은 시작 위치를 여러 번 다시 탐색하게 됩니다.
그래서 메모이제이션을 같이 사용해야 효율적입니다.
핵심 아이디어
문자열의 특정 위치 index에서 시작해서,
가능한 토큰을 하나씩 시도합니다.
흐름은 이렇습니다.
현재 위치에서 만들 수 있는 토큰을 찾는다
토큰이 있으면 그 뒤쪽 문자열을 다시 확인한다
끝까지 성공하면 전체 결과를 반환한다
어떤 토큰으로도 안 되면 null을 반환한다
그리고 이미 확인한 index의 결과는 저장해 두어
다시 계산하지 않도록 합니다.
코드
function restoreTokens(tokens, stream) {
const tokenSet = new Set(tokens);
const memo = new Map();
function dfs(index) {
if (index === stream.length) {
return [];
}
if (memo.has(index)) {
return memo.get(index);
}
for (let end = index + 1; end <= stream.length; end++) {
const currentToken = stream.slice(index, end);
if (tokenSet.has(currentToken)) {
const rest = dfs(end);
if (rest !== null) {
const result = [currentToken, ...rest];
memo.set(index, result);
return result;
}
}
}
memo.set(index, null);
return null;
}
return dfs(0);
}
코드 해설
1. 토큰 목록을 Set으로 바꾸기
const tokenSet = new Set(tokens);
배열 그대로 두면 특정 토큰이 있는지 확인할 때마다 앞에서부터 찾아야 합니다.
Set을 쓰면:
tokenSet.has(currentToken)
처럼 빠르게 확인할 수 있습니다.
2. 이미 확인한 위치 저장하기
const memo = new Map();
memo는 특정 시작 위치에서 문자열을 복원할 수 있는지 저장합니다.
예를 들어 index = 5에서 시작하는 나머지 문자열이
이미 실패라는 걸 알았다면,
다음에 다시 index = 5에 도달했을 때 바로 null을 반환할 수 있습니다.
3. 문자열 끝까지 간 경우
if (index === stream.length) {
return [];
}
끝까지 도달했다는 것은 현재까지의 선택으로 전체 문자열 복원에 성공했다는 뜻입니다.
빈 배열은 "더 붙일 토큰이 없다"는 의미입니다.
4. 현재 위치에서 가능한 토큰 만들기
for (let end = index + 1; end <= stream.length; end++) {
const currentToken = stream.slice(index, end);
현재 위치 index에서 시작해서
끝 위치 end를 하나씩 늘려 가며 토큰 후보를 만듭니다.
예를 들어 stream = "fastapidocs"이고 index = 0이면:
f
fa
fas
fast
fasta
...
fastapi
처럼 확인합니다.
5. 현재 토큰이 사전에 있으면 뒤쪽도 확인
if (tokenSet.has(currentToken)) {
const rest = dfs(end);
현재 토큰이 유효하다면 그 뒤쪽 문자열도 복원 가능한지 재귀적으로 확인합니다.
6. 뒤쪽까지 성공하면 결과 조합
if (rest !== null) {
const result = [currentToken, ...rest];
memo.set(index, result);
return result;
}
현재 토큰도 되고, 뒤쪽 문자열도 성공했다면 정답 배열을 만들 수 있습니다.
현재 토큰을 앞에 붙이고, 뒤쪽 결과를 이어 붙이면 됩니다.
7. 실패한 위치는 null로 저장
memo.set(index, null);
return null;
현재 위치에서 어떤 토큰으로도 전체 복원이 안 된다면 실패로 기록합니다.
이렇게 해두면 나중에 같은 위치를 다시 만났을 때 바로 실패라고 판단할 수 있습니다.
실행 예시
const tokens = ["fast", "api", "fastapi", "docs"];
const stream = "fastapidocs";
console.log(restoreTokens(tokens, stream));
가능한 결과는 다음 중 하나입니다.
["fast", "api", "docs"]
또는
["fastapi", "docs"]
둘 다 올바른 결과입니다.
복잡도
| 구분 | 복잡도 |
|---|---|
| 시간 복잡도 | O(N²) |
| 공간 복잡도 | O(N) |
여기서 N은 문자열 길이입니다.
각 시작 위치에서 가능한 끝 위치를 시도하므로
대략 O(N²)로 볼 수 있습니다.
그리고 memo에 위치별 결과를 저장하므로
추가 공간은 O(N)입니다.
헷갈리기 쉬운 부분
1. 문자열을 앞에서부터 하나씩 잘라보는 건 맞지만, 그대로 재귀만 쓰면 느리다
아이디어 자체는 단순합니다.
하지만 같은 위치를 계속 다시 확인하면 중복 계산이 많아집니다.
그래서 아래 한 줄이 중요합니다.
if (memo.has(index)) {
return memo.get(index);
}
2. 가능한 결과가 여러 개여도 하나만 반환하면 된다
이 문제는 모든 경우를 다 모을 필요가 없습니다.
하나만 찾으면 바로 반환해도 됩니다.
그래서 재귀에서 첫 성공 결과를 만나면 즉시 반환하는 구조로 작성할 수 있습니다.
3. 실패한 위치를 저장하는 것도 중요하다
성공한 결과만 저장하면 안 됩니다.
실패한 시작 위치도 null로 저장해야
나중에 같은 실패를 반복하지 않습니다.
정리
이 문제의 핵심은 공백 없는 문자열을 앞에서부터 가능한 토큰으로 잘라 보면서, 실패한 시작 위치를 다시 계산하지 않도록 하는 것입니다.
즉 구조를 요약하면 다음과 같습니다.
현재 위치에서 토큰 후보 만들기
-> 사전에 있으면 뒤쪽 문자열 재귀 확인
-> 성공하면 결과 반환
-> 실패한 위치는 memo에 저장
겉보기에는 문자열 자르기 문제처럼 보여도, 실제로는 DFS + 메모이제이션 패턴으로 푸는 전형적인 문제입니다.