햄버거 문제

문제 원본 링크

재미있는 문제를 찾았다.
문제의 요구사항 자체는 단순하다. 숫자로 이루어진 배열이 주어졌을때 해당 배열에서 특정 순서로 나열된 숫자의 패턴을 파악하고 그러한 패턴이 몇개 존재하는지 숫자를 세라는 것.

논리가 어렵지 않아서 금방 함수를 떠올릴 수 있었는데 예상외의 부분에서 한참을 애먹었다.

첫번째 풀이

function solution(ingredient) {
    let count = 0;
    const pattern = '1231';
    let ingString = ingredient.join('');

    while (ingString.includes(pattern)) {
        ingString = ingString.replace(pattern, '');
        count++;
    }

    return count;
}

while 문을 사용하여 해당 패턴이 존재하면 문자열에서 그 패턴을 제거하고 카운트를 늘린다는 단순한 발상. 제거할 패턴이 더이상 존재하지 않는 시점에서 while 문에서 탈출하게 된다.

논리적으로 문제는 없으나 위 풀이로는 이 문제가 풀리지 않는다!
ingredient로 주어지는 배열이 엄~청 긴 경우도 있는데 이 경우 시간이 초과해 버리는 것이다.

두번째 풀이

while 문이 시간 초과가 된다면 다른 방식을 써보자 해서 재귀함수를 도입(사실 그냥 얼마전에 공부한 재귀함수를 너무 사용해보고 싶었다).

function solution(ingredient) {
    let count = 0;
    const pattern = '1231';

    function patternRemover(str) {
        if (!str.includes(pattern)) {
            return str;
        }
        count++;
        const newStr = str.replace(pattern, '');
        return patternRemover(newStr);
    }

    patternRemover(ingredient.join(''));
    return count;
}

while 문 썼던것과 비슷하게 패턴이 검출되지 않는것이 재귀함수 탈출 조건이고, 패턴이 검출된다면 count 를 늘리고 패턴을 제거한 string 을 가지고 다시 동일한 함수를 돌린다.

이것도 논리적으로는 문제가 없는 것 같은데 이번엔 또 처음 보는 에러가 나온다

처음 보는 오류라 검색을 해보았는데

1. abort() 함수 호출: 프로그램 내에서 abort() 함수를 명시적으로 호출하여 강제로 종료시키는 경우입니다. 이는 주로 디버깅 목적으로 사용되거나, 프로그램이 치명적인 오류를 감지했을 때 발생할 수 있습니다.
2. 메모리 관리 오류: 잘못된 메모리 접근, 예를 들어 이미 해제된 메모리를 다시 해제하려고 시도하는 경우(double free)나 메모리 할당 오류 등이 발생할 수 있습니다. 이러한 경우 운영체제의 메모리 보호 기법에 의해 프로그램이 강제로 종료됩니다.
3. 스택 오버플로우: 재귀 호출이 너무 깊어져 스택 메모리를 초과하는 경우에도 이 오류가 발생할 수 있습니다. 이는 특히 재귀 함수에서 기저 조건을 제대로 설정하지 않았을 때 흔히 발생합니다.
4. 시스템 리소스 부족: 시스템의 메모리나 다른 리소스가 부족하여 프로그램이 정상적으로 실행되지 못하는 경우에도 이 오류가 발생할 수 있습니다

위 경우에 발생하는 오류라고 한다. 지금은 재귀 호출이 너무 깊어져 스택 오버플로우를 일으키는 상황인 것으로 생각된다.

세번째 풀이

결국 스스로 시도한 두 풀이 모두 실패로 돌아가고 끝내 AI 의 도움을 받아 통과되는 코드를 만들 수 있었다.

function solution(ingredient) {
    const stack = [];
    let count = 0;

    for (const ing of ingredient) {
        stack.push(String(ing)); // 숫자를 문자열로 변환하여 추가

        // 스택의 마지막 4개 요소가 패턴 '1231'과 일치하는지 확인
        if (stack.length >= 4 && 
            stack[stack.length - 1] === '1' &&
            stack[stack.length - 2] === '3' &&
            stack[stack.length - 3] === '2' &&
            stack[stack.length - 4] === '1') {
            // 패턴이 발견되면 스택에서 해당 요소 제거
            stack.splice(stack.length - 4, 4);
            count++;
        }
    }

    return count;
}

스스로 짜낸 코드가 아니고, 주석도 AI 가 달아준 주석을 그대로 가지고 왔다. 중요한 것은 이렇게 스택을 활용하는 패턴을 익히고 학습하는 것일 것이다.

공부하는 김에, 처음 두 풀이가 세번째 풀이보다 느린 이유를 더 살펴보자면 다음과 같다.

1. 문자열 조작 오버헤드: 첫 번째와 두 번째 함수는 replace를 사용하여 새로운 문자열을 반복적으로 생성합니다. 이는 특히 입력 크기가 클 경우 계산 비용이 많이 듭니다. replace를 호출할 때마다 새로운 문자열이 생성되므로 시간 복잡도가 증가합니다.
2. 재귀 호출: 두 번째 함수는 재귀를 사용하며, 이는 함수 호출 관리로 인해 오버헤드를 추가하고, 매우 깊은 재귀의 경우 스택 오버플로우가 발생할 수 있습니다.
3. 스택의 효율성: 세 번째 함수는 스택을 사용하여 요소를 관리하고 마지막 네 개의 요소만 패턴 '1231'과 일치하는지 확인합니다. 이 접근 방식은 새로운 문자열을 생성하지 않고 스택을 직접 수정하므로 시간과 공간 측면에서 더 효율적입니다.
4. 점진적 처리: 각 요소를 점진적으로 처리하고 완전한 패턴이 발견될 때만 스택을 수정함으로써 불필요한 작업을 최소화합니다.

전부다 납득이 가는데 '시간 복잡도가 증가한다' 라는 표현이 생소하다. 다음 공부 주제는 이걸로 하자!