문제
메모
풀이 방법 1
코드에는 문제가 없는 것 같은데 계속해서 시간 초과가 떠서 당황했던 문제이다. 처음엔 시간 초과의 원인이 for문이나 splice()에 있는 줄 알고 한참을 헤맸다. 그런데 시간 초과의 원인은 연속된 4개의 요소를 삭제한 뒤 i를 -1로 초기화했기 때문이었다. 다시 말해 배열에서 splice()를 통해 요소를 삭제할 때마다 i가 -1로 초기화되면서 for문이 완전히 처음부터 다시 시작되고 있었던 것이다. 그러나 배열에서 변경된 부분은 일부 삭제된 요소에만 해당되므로 i를 -1로 설정할 필요는 전혀 없다. i를 -1이 아니라 i - 3으로 설정(삭제된 4개의 요소 바로 앞)하자 시간 초과 문제가 해결되어 정답 처리되었다.
풀이 방법 2
스택을 활용하면 훨씬 쉽다. 재료를 stack 배열에 하나씩 입력하고, 요소가 4개 이상 쌓이면 버거가 완성되었는지 확인한다. 버거는 1, 2, 3, 1이 연속해서 나타나야 한다. 그래서 stack 배열의 뒤에서부터 요소 4개를 slice로 잘라내 문자열로 만든 뒤, 그 문자열이 "1231"이면 버거가 완성된 것이다. 이 경우 정답에 1을 더해주고, splice를 활용해 stack 배열 뒤에서부터 4개의 요소를 삭제한다. slice와 splice 메서드의 괄호 부분에 "-숫자"를 입력하면 뒤에서부터 잘라내거나, 삭제할 수 있다. 이를테면 stack.splice(-4)는 stack 배열 뒤에서부터 4개의 요소를 삭제한다는 뜻이다.
정답
// 풀이 방법 1
function solution(ingredient) {
let answer = 0;
for (let i = 0; i < ingredient.length; i++) {
// 연속된 4개의 요소가 [1, 2, 3, 1]이면 이 부분을 삭제한다
// 그러고 나서 answer에 1을 더한다
// 원본 배열이 바뀌었으므로 삭제된 부분 앞에서부터 다시 체크해야 한다
// 따라서 i를 i - 3으로 설정한다
if (
ingredient[i] === 1 &&
ingredient[i + 1] === 2 &&
ingredient[i + 2] === 3 &&
ingredient[i + 3] === 1
) {
ingredient.splice(i, 4);
answer++;
i = i - 3;
}
}
return answer;
}
// 풀이 방법 2
function solution(ingredient) {
const stack = [];
let answer = 0;
for (let i = 0; i < ingredient.length; i++) {
stack.push(ingredient[i]);
if (stack.length >= 4) {
const perfectBurger = stack.slice(-4).join("") === "1231";
if (perfectBurger) {
stack.splice(-4);
answer++;
}
}
}
return answer;
}
반응형