코딩테스트 - 햄버거 만들기(알고리즘 이해)

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

프로그래머스

프로그래머스 햄버거 만들기 문제를 풀면서 알고리즘에 대해 생각하게 되었습니다.

 

문제 설명

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

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

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

---

제한사항

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

---

입출력 예ingredientresult

ingrdient	result
[2,1,1,2,3,1,2,3,1]	2
[1,3,2,1,2,1,3,1,2]	0

 

처음 작성한 식

function solution(ingredient) {
    var answer = 0;
  let hamburger = ingredient.join('')

  while(hamburger.includes(1231)){
   hamburger = hamburger.replace(1231,'')
    answer ++
  }
    return answer;
}

ingredient 를 하나의 string으로 만들고 while문을 작성해서 햄버거에 1231 재료가 있으면 계속 1231 재료를 빼라는 명령어를 줬습니다.

하지만.... 제출 후 채점을 해보니 시간 초과라는 에러가 잔뜩 뜨고 코드가 제대로 실행이 되지 않았습니다.

 

그래서 두 번째 풀이로...

 

두 번째 풀이

function solution(ingredient) {
    var answer = 0;
    const temp = [];

    for (let i = 0; i < ingredient.length; i++){

        temp.push(ingredient[i]);

        if (temp.length >= 4){
            if (temp[temp.length-4] == '1'
               && temp[temp.length-3] == '2'
                && temp[temp.length-2] == '3'
                && temp[temp.length-1] == '1'
               ) {
                temp.pop();
                temp.pop();
                temp.pop();
                temp.pop();

                answer++;
            }
        }

    }
    return answer;
}

이번에는 하나하나 새로운 배열에 넣어 배열에 추가된 재료들을 확인하면서 햄버거의 숫자를 counting하니까 제대로 작동을 하더라고요.

 

생각한 점

어???라???? 뭔가 이상함을 느낍니다. 어떻게 해서든 답을 내려고 했던 저에게 이러한 시련이 찾아오다니요. 그래서 두개의 차이점을 비교해봤는데,  개인적으로 반복되는 것은 같은데 왜 이렇게 속도차이가 날까? 부터 시작되었습니다.

조건에 백만개의 재료까지 허용된다는 것을 보고 만약 재료가 백만개면 최대로 햄버거가 만들어지는 갯수는 25만개 입니다. 그럼 최대 25만번 저기 위에있는 while 문이 최대 25만번 반복이 되는데 또 문제가 있습니다.

처음에는 백만자리의 숫자를 확인하고 다음번에는 백만 -4 자리의 숫자를 확인하고, 또 이것이 계속 반복되야만 끝나는 함수가 되어버립니다. 그렇다면 당연히 엄청난 숫자를 확인하겠죠. n + (n-4) + (n-8)+(n-12)+ .....

 

저의 소견이기 때문에 정답은 아닙니다ㅎㅎ

그리고 두번째 작성한 코드는 배열에서 하나씩 새로운 배열에 넣어서 비교하는 과정을 가집니다. 그렇게되면 재료의 갯수만큼만 비교를 딱 할 수 있어서 n번만 하면 됩니다.

 

이렇게 시간 복잡도는 같지만? 상수값이 너무나도 많이 차이나서 이런 현상이 생기나봐요. 정답은 아니겠지만 제 머리 이론상을 그러하답니다 ㅎㅎ 

 

답변해주실 분 구합니다. 감사합니다.