프로그래머스 코딩테스트, 햄버거 만들기 (Javascript)

부끄러움 혹은 후련함 그 어딘가

 

 

문제 설명 (링크)

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

 

 

제한 사항

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

 

 

입출력 예

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

 

 

 

풀이

function solution(ingredient) {

  let answer = 0;

  const stack = [];

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

    stack.push(ingredient[i]);

    const target = stack.slice(-4);

    if (target.join("") !== "1231") {

      continue;

    }

    stack.pop();

    stack.pop();

    stack.pop();

    stack.pop();

    answer++;

  }

  return answer;

}

 

 

 

 

소감

 총 4번의 각기 다른 코드를 짜보면서 느낀 점은,

1) 필수 요구사항을 적는다.

2) 어떻게 짤 것인지 계획을 적는다.

3) 이 문제의 의도 or 고려해야할 점을 체크한다.

4) 다시 짜야할 때는 기록해두고 다 지우고 새로 짠다 -> 누더기처럼 기워서 짜지 말자

 

우선 각기 작성했던 코드를 적어보면, 아래와 같다. 요즘 1번과 2번을 연습 중인데, 3번도 함께 연습해보려고 한다.

회차	코드	비고
1차 오답 66.7 / 100	function solution(ingredient) {             let answer = 0,          val = ingredient.join(''),          lastCount = val.length;          do {     // 스플릿한 배열 array 선언         const array = val.split('1231');     // array.length -1 을 lastCnt로 저장         lastCount = array.length - 1;         answer += lastCount;         val = array.join('');              } while (lastCount !== 0);     // lastCnt === 0 이면 for 문 break,     //         !== 0 이면 다시 스플릿한다.              return answer; } // 빵 > 야채 > 고기 > 빵 ==> 1231	다만, 빠뜨렸던 요구사항은 n번째 재료가 쌓였을 때 바로 포장한다는 내용이였다. split은 여러개의 1231 묶음이 동시에 존재할 때 오류가 있었다. 예를 들어 [1,1,1,2,3,1,2,3,1,2,3,1,2,3,1]의 경우 split은 [1,1,1,2,3,1,2,3,1,2,3,1,2,3,1] 이렇게 짝을 지어 2개를 반환하게 된다. (문제의 의도대로 하면 답은 3개여야 한다.)
2차 오답 83.3 / 100	function solution(ingredient) {     let answer = 0,          orignal = ingredient.join(''),          replaced;          while (orignal !== replaced) {         replaced = orignal.replace('1231', '');                  if (orignal !== replaced) {             orignal = replaced;             replaced = undefined;             answer++;         }     }               return answer; }	앞에서부터 차근차근 체크하는 것으로 변경하니, 이번에는 시간초과가 났다. 제한조건의 '1 ≤ ingredient의 길이 ≤ 1,000,000'을 봤을 때, 시간을 고려해야 되는구나! 하고 생각했다면 좋았을 텐데 다시 짰다.
3차 오답 38.9 / 100	function solution(ingredient) {     let answer = 0;          // 배열이 너무 길어서 오래걸린다. 앞에 필요없는 애들을 짤라내 버리자     // '1231'이 존재하는? index를 구해서      // 0 ~ index + 4  --> index + 4, s.length 까지만으로 찾을 대상 문자열을 바꾸자     // indexOf === -1 일 때까지           const original = ingredient.join('');     let current = original, prev;     for (let i=0 ; ; i++){         const prevStr = prev ? prev.substring(prev.length - 3) : '';         const index =  (prevStr + current).indexOf('1231');         if (index === -1) {             break;         }                  prev = current.substring(0, index);         current = current.substring(index + 4);         answer++;     }          return answer; }	replace는 indexOf와 동일하게 앞에서 순차적으로 돈다. 따라서 찾은 n번째보다 앞의 문자열은 더이상 검사할 필요가 없다는 뜻이였다. 이미 체크가 끝난 문자열(prev)와 체크를 계속해서 해야 하는 문자열(current)를 나누어서 관리하자. 다만 prev의 일부와 연결되어 1231이 완성될 수도 있으니 일부를 계속 떼어주자.  -> 하지만 prev 관리가 어려웠고, 일부 케이스에서 prev 길이가 0 ~4 사이일 때 동일한 문자열이 반복해서 들어가는 오류가 있었다.
4차  오답 88.9 / 100	function solution(ingredient) {   let answer = 0;   // 배열이 너무 길어서 오래걸린다. 앞에 필요없는 애들을 짤라내 버리자   // '1231'이 존재하는? index를 구해서   // 0 ~ index + 4  --> index + 4, s.length 까지만으로 찾을 대상 문자열을 바꾸자   // indexOf === -1 일 때까지   const original = ingredient.join("");   let current = original;   for (let i = 0, nth = 0; ; i++) {     const startNth = Math.max(nth - 3, 0);     const target = current.substring(startNth);     const index = target.indexOf("1231");     if (index === -1) {       break;     }     const prev = current.substring(0, startNth + index);     current = prev + target.substring(index + 4);     nth = index;     answer++;   }   return answer; }	prev 관리만 조금 더 잘한다면? 하고 디버깅으로 오류를 잡아봤다. 하지만 실패! 4차쯤 되니까 정말 포기하고 답을 볼까도 생각했었다. 동시에 여기까지 왔는데 포기하는 것도 아까워서 정말 다 덮어놓고 생각해보기로 했다.
5차 정답 100 / 100	function solution(ingredient) {     let answer = 0;     const stack = [];     for (let i=0 ; i < ingredient.length ; i++) {         stack.push(ingredient[i]);                  const target = stack.slice(-4);         if (target.join('') !== '1231') {             continue;         }                  stack.pop();         stack.pop();         stack.pop();         stack.pop();         answer++;     }     return answer; }	프로그래머스 질문하기로 갔다가 https://school.programmers.co.kr/questions/73850 이글을 보게되었다. stack... 하..... 내가 stack을 떠올리기만 했어도 이렇게 돌아돌아 오진 않았을텐데. 마지막의 요소에 접근할 수 있는 방법하면 한동안은 stack 부터 떠올릴 것 같다.