[TIL #6] 햄버거 만들기

패턴 매칭을 할 수 있느냐를 물어보는 문제다.

1. 빵
2. 야채
3. 패티

의 3개의 재료가 있고, 무조건 [1, 2, 3, 1]의 조합만 인정한다.

재료의 목록을 담은 배열이 주어질 때 얼마나 효율적으로 패턴 검사를 할 수 있는지 물어보는 문제.

 

패턴 매칭 문제에 익숙하지 않은 모두가 이렇게 생각할 것이다.

일단 배열 전체를 돌며 검사하자!

나도 마땅한 방법이 생각나지 않아서 그렇게 했다.

 

// 1 : 빵
// 2 : 야채
// 3 : 패티

function solution(ing) {
    let answer = 0;
    const pattern = [1, 2, 3, 1];
    
    const ingLen = ing.length;
    
    for (let i = 0; i <= ingLen - 4; i++) {
        if (ing.slice(i, i + 4).join('') === pattern.join('')) {
            ing.splice(i, 4);
            i -= 4;
            answer++;
        }
    }
    
    return answer;
}

이건 100점짜리 정답이 아닌 줄 알면서도,

다른 방법이 떠오르지 않아 일단 이렇게 했다.

시간도 최대 8초까지 걸리는 참사가 일어났다.

 

그러던 와중 너무나도 당연한 사실을 간과하고 있었다.

괄호 매칭이나 전/후위연산자 처리처럼 스택을 사용할 수 있다는 것을...

괄호 매칭과 사실상 똑같은 건데 보이는 게 다르니 떠올리지 조차 못했던 것 같다.

 

스택을 사용하면 이렇게 된다.

// 1 : 빵
// 2 : 야채
// 3 : 패티

function solution(ing) {
    const pattern = [1, 2, 3, 1];
    const stack = [];
    let answer = 0;
    
    for (let i = 0; i < ing.length; i++) {
        stack.push(ing[i]);
        
        if (stack.length >= 4 && stack.slice(-4).join('') === pattern.join('')) {
            stack.splice(-4);
            answer++;
        }
    }
    
    return answer;
}

코드도 간결해지고 효율도 매우 좋아졌다.

최악의 경우의 처리속도는 거의 27배에 가까이 개선됐다.

 

각 테스트 케이스를 처리하는 데 시간이 얼마나 걸렸는지 확인하는 게 정말 큰 자극이 된다.

어떻게든 10초 이내에 통과는 시킬 수 있지만, 그건 반쪽짜리 정답이니까.

처리 속도까지 챙겨야 진짜 발전하는 게 아닐까.