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

https://school.programmers.co.kr/learn/courses/30/lessons/133502#qna

프로그래머스

---

[문제]

 

문제 설명

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

---

제한사항

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

---

입출력 예ingredientresult

[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

 

---

[풀이]

 

앞쪽부터 제거하면서 나아가는 식으로 문제를 풀 수 있습니다.
그런데 이렇게 하면 햄버거를 만들 수 있는 부분을 제거한 다음, 다시 첫 스타트 찾을 때...
이 문제의 경우 인덱스를 0으로 놓으면 시간 초과가 나옵니다.
또한 이렇게 풀었을 경우 최적화 하기가 어렵습니다..
그런데....배열이나 리스트를 하나 더 만들어 보는건 어떤신지..?

tmp = []; 라고 하나를 선언하는 겁니다.

 

일단 시간 초과의 경우의 코딩의 흐름 과정은 아래와 같습니다.
제거되는 과정을 자필로 쓰면서 설명 해보자면

테스트 케이스1 의 경우,
[2, 1, (1, 2, 3, 1), 2, 3, 1]에서 괄호 친 부분 제거.. 그 후 다시 인덱스를 0부터 시작하거나 우리가 원하는 1의 값이 있는 인덱스를 찾기가 어려울 수 있습니다.

 

그렇다면..제가 제시하는 풀이의 경우는..
tmp = [];
[2, 1, 1, 2, 3, 1, 2, 3, 1] 가 주어질 때
tmp가 4개 이상이 됐을 때 삭제되는 재료 상황인지 체크하는 방식입니다.
tmp = [2, 1, 1, 2] 하나 쌓고, 해당 상황 됐을 때 체크 당연히 불가능..
계속 쌓아가면서.. 체크를 반복 하다가
tmp = [2, 1, (1, 2, 3, 1)] 이 상황일 때, tmp.length 에서 - 4 만큼 구간을 체크하는 거죠.. 그럼 햄버거를 만들 수 있죠..? ans++;

tmp = [2, 1] 맞는 재료는 제거해주고, 다시 하나씩 쌓아가면서
ingredient.lenght 까지 for문 돌려서 푸는 것도 방법 같습니다.

 

다른 좋은 풀이도 있겠지만.. 머.. ㅎㅎㅎ.. 혹시 헤매는 분들이 있을까 해서 글을 남겨 봅니다.

 

 

---

 

[ 틀린 풀이들 ]

 

 

function solution1(ingredient) {
    var answer = 0;
    
    var idx = 0;
    var ans = "1231"
    while(true) {
        if (idx === ingredient.length) break;
        
        if (ingredient[idx] === 1) {
            var startIdx = idx;
            var i = 0;
            var tmp = "1";
            while (true) {
                if (tmp.length === 4) {
                    answer++;
                    var endIdx = idx;
                    var arr = [];
                    ingredient = arr.concat(ingredient.slice(0, startIdx), ingredient.slice(endIdx + 1, ingredient.length));
                    // arr.indexOf(1)
                    // var tmp = ingredient.slice(0, startIdx)
                    // var newStart = tmp.lastIndexOf(1);
                    idx = 0;
                    break;
                }
                idx++;
                i++;
                if (ingredient[idx] === parseInt(ans[i % 4])) {
                    tmp += String(ans[i % 4])
                    continue;
                    
                } else {
                    break;
                }
                
            }
        } else {
            idx++;
        }
        
    }
    return answer;
}


function solution2(ingredient) {
    var answer = 0;
    
    var idx = 0;
    var ans = "1231"
    var last = ingredient.length;
    while(true) {
        if (idx === last) break;
        
        if (ingredient[idx] === 1) {
            
            var candi = ingredient[idx] + String(ingredient[last - 3]) + String(ingredient[last - 2]) +
                String(ingredient[last - 1])
            
            if (candi === ans) {
                answer++;
                idx++;
                last -= 4;
            }
        } else {
            idx++;
        }
        
    }
    return answer;
}

 

 

 

---

 

[코드]

 

function solution(ingredient) {
    let answer = 0;
    let tmp = [];
    const ans = "1231";

    for (let i = 0; i < ingredient.length; i++) {
        tmp.push(ingredient[i]);
        // 길이가 4 이상일 때부터 햄버거를 만들 수 있는지 뒤에서 부터 체크 하는 형식
        // 이런식으로 해서 앞에서 부터 pop할 때 다시 start지점을 찾는 부분을 최적화 되는 원리
        if (tmp.length >= 4) {
            let candi = tmp.slice(-4).join('');
       
            if (candi === ans) {
                answer++;
                for (let j = 0; j < 4; j++) {
                    tmp.pop();
                }
            }
        }
    }

    return answer;
}

 

 

---

후기

 

오랜만에 코테 풀이 포스팅이네요..

레벨에 비해 나름 시간이 걸려서 억울해서라도

기억 해두려고 포스팅 합니다ㅋㅋㅋ