햄버거 만들기

프로그래머스 햄버거 만들기

 

주어지는 ingredient배열 중 1, 2, 3, 1 순서로 되어있는 요소를 제거하고, 다시 제거된 배열에서 1, 2, 3, 1이 없을때까지 해당 순서의 개수를 찾는 문제이다.

 

 

 

먼저 작성한 코드

function solution(ingredient) {
    var answer = 0;
    let ingredientStr = ingredient.join('')+''
    if (ingredientStr.includes(1231)) {
        do {
            ingredientStr = ingredientStr.replace(1231, '')
            answer++
        } while (ingredientStr.includes(1231))
    }
    return answer;
}

주어지는 배열을 문자열화 시키고, 첫 구문은 무조건 실행되는 do while의 특징때문에 if문을 사용하여 첫 번째에도 1231을 포함하는지 판별한 뒤 do while을 실행하였다.

포함한다면 1231부분을 제거하고 answer에 1을 더하는 형식으로 정답을 반환하였다.

시간초과로 실패하였다.

처음부터 includes, 반복마다 incldues, replace를 하다보니 시간복잡도 측면에서 문제가 발생하는것으로 판단하였다.

 

 

 

두번째로 작성한 코드

function solution(ingredient) {
    var answer = 0;
    let ingredientStr = ingredient.join('')+''
    if (ingredientStr.includes(1231)) {
        while (true) {
            ingredientStr = ingredientStr.replace(1231, '')
            answer++
            if (!ingredientStr.includes(1231)) break;
        }
    }
    return answer;
}

별 다를것 없는 코드이다. do while에서 while문으로 바꾼건데 한 테스트가 왜 통과되었는지도 모르는...

어쨋든 성공은 하나, 같은 시간초과 실패

 

 

세번째로 작성한 코드

function solution(ingredient) {
    var answer = 0;
    let temp = [];
    
    for (let i = 0; i<ingredient.length; i++) {
        temp.push(ingredient[i])
        if (temp.length >= 4) {
            let tempBurger = temp.slice(-4).join('')
            if (tempBurger === '1231') {
                temp.splice(-4)
                answer++
            }
        }
    }
    return answer;
}

어쨋든 반복문 내에서 includes를 사용하니 시간초과가 계속된다 생각하여 다른 방식으로 접근해보았다.

빈 배열을 만들어주고, 각 재료를 해당 temp배열에 넣어준다. 배열의 길이가 4를 넘을때 해당 배열에 대한 검사를 진행한다.

tempBurger을 뒤에서 4개의 요소를 합친것으로 만들어주고, tempBurger가 1231일때 temp배열에서 해당 요소들을 제거해준뒤 answer에 1을 더한다.

 

테스트코드로 들어오는 [2, 1, 1, 2, 3, 1, 2, 3, 1] 배열을 살펴보자.

temp에 [2, 1, 1, 2]가 들어왔을 때 if문 조건에 해당하지만, 1231이 아니기때문에 햄버거가 완성되진 않는다.

[2, 1, 1, 2, 3, 1]까지 들어오면 뒤에서 4개인 [1, 2, 3, 1]이 중첩조건문을 통과하여 temp가 [2, 1]이 되고 answer에 1이 더해지는것이다.

그리고 반복문이 진행되어 [2, 1, 2, 3, 1]이 되었을 때 동일하게 진행되어 temp가 [2]가 되고 answer에 1이 더해진다.

최종적인 temp는 [2]이고 검색이 끝나 answer을 리턴한다.

---

includes메서드를 사용하면 최대길이의 배열을 계속해서 탐사하기때문에 시간복잡도 측면에서 문제가 되었던 것으로 생각된다.

해당 방법은 길이가 4이상일때만, 최소탐사를 진행하여 문자열이 같은지 판단하기때문에 시간복잡도에서 우월하다고 생각한다.