[백준 9935] 문자열 폭발 (Node.js)
March 25, 2022
문제
문제 풀이
Stack을 활용해 문제를 풀 수 있다. 처음에 splice 를 활용해서 푼 풀이는 푼 속도는 빨랐지만 소요시간이 거의 푼 사람들 중에서는 꼴찌였다.
다시 생각해서 문제를 풀었다. 문제의 조건으로 주어진 target 문자열의 마지막 길이를 기준으로 일치하는 문자열이 있는지를 string 을 순회해서 탐색하고, 만약 해당 문자열의 길이가 같으면 더 탐색할 가치가 있다고 판단해 string의 시작 문자열까지 같은지 탐색하는 방법을 활용했다.
target문자열의 길이만큼 순회할 때는 flag 변수를 두어 같은지를 확인하고 첫 번째 문자열까지 탐색 후 pop 조건을 만족한다면 stack에서 target의 길이보다 1 적은 수만큼 제거해준다.
Recap
처음 풀이는 15분정도가 소요되어 뿌듯함을 가지고 채점을 했는데 시간이 너무 오래 걸렸다. 다시 살펴보니 순회 1회당 N^2의 시간복잡도를 가졌고 결과적으로는 N^3의 시간복잡도를 갖게되었다. 배열을 조작할 때 splice와 slice를 사용해서 발생한 문제였다.
좀 더 문제가 원하는 풀이방향을 고민해보고 문제를 풀 필요가 있어보인다. 새롭게 푼 풀이에서는 비교 대상을 잘못 선정해 해결하느라 시간이 좀 소요됐다. 비교할 대상을 string 문자열을 stack이라고 지정해서 발생한 문제였다. 시간은 좀 더 소요됐지만 좋은 풀이를 고민해보고 문제를 해결하기 위해 끝까지 붙잡고 고민해 보람을 느낄 수 있었던 문제풀이였다.
Code
// BAEKJOON
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
// VSCODE : TEST_CASE 폴더 생성 후, 원하는 테스트 케이스를 index.txt 에 작성
const input = require('fs')
.readFileSync('TESTCASE/index.txt')
.toString()
.trim()
.split('\n')
const log = console.log
// 1560ms
const solution1 = input => {
const [string, target] = input
const targetL = target.length
const stack = []
for (let i = 0; i < string.length; i++) {
stack.push(string[i])
while (targetL <= stack.length) {
const temp = stack.slice(-targetL).join('')
if (temp === target) stack.splice(-targetL, targetL)
else break
}
}
log(stack.length > 0 ? stack.join('') : 'FRULA')
}
// 312ms
const solution2 = input => {
const [string, target] = input
const targetL = target.length
const stack = []
for (let i = 0; i < string.length; i++) {
if (target[targetL - 1] === string[i]) {
let flag = true
for (let j = 1; j < targetL; j++) {
if (target[targetL - 1 - j] !== stack[stack.length - j]) {
flag = false
stack.push(string[i])
break
}
}
if (flag) {
let count = targetL - 1
while (count--) stack.pop()
}
} else stack.push(string[i])
}
log(stack.length > 0 ? stack.join('') : 'FRULA')
}
solution2(input)
