split의 폐해!
function solution(ingredient) {
const hamburger = '1231';
let iStr = ingredient.join('');
let count = 0;
while (true) {
if (!iStr.includes(hamburger)) return count;
const splited = iStr.split(hamburger);
count += splited.length - 1;
iStr = splited.join('');
}
}66점...
반례가 필요했다.
INPUT : [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1]
OUTPUT : 5
위 예시를 내가 이해한 로직으로 잘라보면 결과값은 4였다. 그렇다, 내가 정확히 이해하지 못한 부분이 존재했다. 앞에서부터 차례차례 반복하면서 자르는 것과 처음 보이는 것을 한 번에 모두 자르고나서 반복하는 것에는 차이가 존재했다. 위의 문제는 전자에 맞게 풀어야한다. 문제 내용도 재료가 쌓여있고 그 중에서 맞는 재료를 빼내는 형태로 서술되어 있다. 마치 같은 모양의 풍선을 터뜨리면 위에서 다른 풍선이 내려오고 그 때 위아래 비교하여 또다시 같은 모양으로 만나게 되면 연속으로 터지는 그런 게임 같은 것을 말하고 있었다.
function solution(ingredient) {
const hamburger = '1231';
let iStr = ingredient.join('');
let count = 0;
while (true) {
if (!iStr.includes(hamburger)) return count;
iStr = iStr.replace(hamburger, '');
count++;
}
}시간초과
replace가 아주 성능이 안좋은 메소드이긴하다. replace 자체도 내부적으로 순회를 하는 것 같다. 메소드의 문제인가 싶어서 아래처럼 수정해보았다.
function solution(ingredient) {
const hamburger = '1231';
let iStr = ingredient.join('');
let count = 0;
while (true) {
if (!iStr.includes(hamburger)) return count;
const start = iStr.indexOf(hamburger);
iStr = iStr.slice(0, start) + iStr.slice(start + hamburger.length);
count++;
}
}요것도 시간초과
질문을 좀 찾아보니... 그냥 배열인 상태로 하는편이 성능이 더 좋아진다고 한다. 생각해보면 위에 적은 코드들은 최악인 경우, 1000000 * 1000000 = 1000000000000. (while * indexOf) 이러한 시간복잡도를 갖게 될 수 있다. 그냥 한번의 순회로 답을 찾을 수 있도록 변경해야겠다.
포인트는 스택이였다. 사실 맨 처음에 이 문제를 읽고 스택으로 문제를 접근하면 될까 하는 생각이 스쳐지나갔었다. 결국 다시 돌아왔다. for문 한 번으로 체크할 수 있는 방법은 스택의 개념을 사용하는 것이였다.
function solution(ingredient) {
const stack = [];
let count = 0;
for (let i = 0; i < ingredient.length; i++) {
stack.push(ingredient[i]);
if (stack.length >= 4) {
if (
stack[stack.length - 1] === 1 &&
stack[stack.length - 2] === 3 &&
stack[stack.length - 3] === 2 &&
stack[stack.length - 4] === 1
) {
count++;
stack.splice(stack.length - 4, 4); // ✅
}
}
}
return count;
}체크박스 부분에서 스택의 의미를 살려 pop()을 4번해도 되지만, splice를 통해서 좀 더 중복없는 코드로 구현해보았다. 어차피 같은 의미!