(JavaScript) 햄버거 만들기

주어진 숫자 배열에서 1, 2, 3, 1 패턴의 갯수를 구하는 문제.

 

1. 주어진 ingredient를 string으로 바꿔서 String.prototype.indexOf 함수를 가지고 패턴을 찾는 방법

패턴의 인덱스를 찾은 다음에는 replace함수를 통해 해당 부분을 지우고, 다시 패턴을 찾는다.

더이상 패턴이 발견되지 않을때까지 반복한 뒤, answer를 반환한다.

=> 시간초과

s = s.replace 연산이 오래 걸리는 문제인가 싶어서 배열로 다시 시도해보기로 한다.

function solution(ingredient) {
    var answer = 0;
    var s = ingredient.join('');
    while(true){
        var c = s.indexOf("1231");
        if(c === -1){
            break;
        }
        answer++;
        s = s.replace("1231", "");
    }
    return answer;
}

 

2. 주어진 배열에서 findIndex 함수를 통해 패턴을 찾는 방법.

패턴의 인덱스를 찾은 다음에는 splice함수를 통해 해당 부분을 지우고, 다시 패턴을 찾는다.

더이상 패턴이 발견되지 않을때까지 반복한 뒤, answer를 반환한다.

=> 시간초과

string이나 배열의 문제는 아닌듯하니 반복문 부분에서 생긴 문제같다.

패턴을 반복해서 찾는 과정에서 최대 n^2까지 반복하게 된다. (예를 들어 11111231231231231231 같은 경우)

function solution(ingredient) {
    var answer = 0;
    
    while(true){
        var i = ingredient.findIndex((element, index, array) => {
            return array[index] === 1 &&
                array[index+1] === 2 &&
                array[index+2] === 3 &&
                array[index+3] === 1;
        })
        if(i === -1){
            break;
        }
        answer++;
        ingredient.splice(i, 4);
    }
    return answer;
}

 

3. 패턴을 찾은 후 다시 처음부터 패턴을 찾기보다, 패턴의 인덱스에서 -3만큼 되돌아간 위치에서부터 다시 찾기로 한다.

왜냐면 내가 찾는 패턴의 길이는 4이고, 인덱스를 -4 이상 되돌아가봤자 어차피 패턴을 찾을 수 없을 것이기 때문이다. 만약 -4 이전에 패턴이 있었다면 현재 인덱스까지 오기 전에 이미 찾았을 것이고, 그렇다면 배열에서 삭제했을 것이다.

이렇게 하면 최대 4n의 시간이 걸리게 된다(사실상 n)

function solution(ingredient) {
    var answer = 0;
    
    for(i = 0; i < ingredient.length; i++){
        if(ingredient[i] === 1 &&
            ingredient[i+1] === 2 &&
            ingredient[i+2] === 3 &&
            ingredient[i+3] === 1){
            answer++;
            ingredient.splice(i, 4);
            i-=3;
        }
    }
    return answer;
}

=> 성공