Javascript - 햄버거 만들기 [Level: 1]

 

 

 

햄버거 만들기

햄버거는 쌓아서 만든다는 특징이 있다... 쌓는다 !

 

이 문제는, stack 의 풀이를 사용할 것을 유도하고 있다.

 

 last in , first Out 

마지막에 들어온 데이터가 가장 먼저 빠져온다. 

그렇기 때문에, 스택 구조는 시간 복잡도 면에서 유리하다.

데이터가 위쪽에 쌓이는 형태이기 때문에 PUSH (O)n 

나가는 것도 맨 위쪽이기 때문에 POP (O)n 이기 때문이다.

 

 

 

우선 stack 배열을 만들고, 

주어진 배열 ingredient 를 순회하며 앞에서 부터 하나씩 쌓는다. Stack !

 

 

하나쌓을 때 마다, stack 배열의  뒤에서부터 4개의 값을 조사한다. 

1231 일 경우, 햄버거를 만들 수 있으므로, answer ++ 를 해주고,

조립한 햄버거 재료를 제외한다.

다시 반복문으로 돌아가 다음 재료 stack에 추가한다 ... 반복

 

이렇게 하면, 문제의 핵심인

 

1231이 아니어서 지나친 재료가  다시 1231의 재료가 될 수 있는 부분 

12  1231 31    << 와 같은 경우 또한 정상적으로 조립 대상에 포함할 수 있다.

12 1231 에서 answer ++  후 1231 제거

12 3 

12 3 1  에서 answer ++  후 1231 제거