1차 시도
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\\n');
function run(input: [string, number, ...string[]]) {
const [string, num, ...commands] = input;
let cursor = string.length;
let result = string;
for (const command of commands) {
switch (command[0]) {
case 'L':
if (cursor !== 0) cursor -= 1;
break;
case 'D':
if (cursor !== string.length) cursor += 1;
break;
case 'B':
if (cursor !== 0) {
result = result.slice(0, cursor - 1) + result.slice(cursor);
cursor -= 1;
}
break;
case 'P':
result =
result.slice(0, cursor) + command.at(-1) + result.slice(cursor);
cursor += 1;
break;
default:
break;
}
}
return result;
}
console.log(run(input));
- 문자열을 그대로 이용
- 시간초과 -
slice
를 이용한 문자열 병합이 각각 O(n)의 시간복잡도를 가짐
- 시간복잡도 O(n*m)
- L, D = O(1)
- B, D = O(n)
- 명령의 길이와 주어진 스트링의 길이에 따라 최대 O(n*m)의 시간복잡도를 가진다.
개선
function run(input: [string, number, ...string[]]) {
const [initialString, num, ...commands] = input;
const leftStack: string[] = initialString.split('');
const rightStack: string[] = [];
for (const command of commands) {
const isNotEmptyLeftStack = leftStack.length > 0;
const isNotEmptyRightStack = rightStack.length > 0;
switch (command[0]) {
case 'L':
if (isNotEmptyLeftStack) rightStack.push(leftStack.pop()!);
break;
case 'D':
if (isNotEmptyRightStack) leftStack.push(rightStack.pop()!);
break;
case 'B':
if (isNotEmptyLeftStack) leftStack.pop();
break;
case 'P':
leftStack.push(command.at(-1)!);
break;
default:
break;
}
}
return leftStack.join('') + rightStack.reverse().join('');
}
- 커서의 위치를 기준으로 스택을 나눈다고 생각 (배열 이용)→ 훨씬 코드가 간결해짐
push
+ reverse
vs shift
shift
는 전체 배열이 계속 재정렬되기 때문에 O(n)의 시간복잡도가 반복되어 발생
- 마지막에만
reverse
하면 한번만 재정렬하기 때문에 비교적 효울적
- 시간복잡도 O(m+n)
push
, pop
→ O(1) 즉, L,D,B,P = O(1)
- 명령의 길이와 주어진 스트링의 길이에 따라 최대 O(n + m)의 시간복잡도를 가진다.