스택(stack)에 대해서 알아보자 (feat.햄버거 만들기)

우리가 글을 쓰다가 취소하고 싶으면?

보통

ctrl + z를 누를것이다.

일명 되돌리기를 통해 취소하는것인데, 스택형 자료구조도 이와 같다.

홈페이지에서 뒤로가기 버튼도 마찬가지!

stack은 데이터를 한 줄로 쌓아서 탑을 쌓듯이 추가하는 형태이다.

stack의 맨 위에 데이터를 추가하는건 push

반대로 맨 위의 데이터를 제거하는건 pop이라고 한다.

우리가 어렸을 때 자주 하던 블록 놀이를 생각해보면 이미지를 떠올리기 쉽다.

이에 대해서, 시간 복잡도도 알아보자

시간복잡도 Blg-O와 관련지어서 알아보면, 스택이 아무리~크고~거대해도!

자료를 삽입하기 위해서는 우리는 딸-깍 한 번만 해도 된다.

이렇게 되면 시간 복잡도는 O(1)이 된다.

삭제를 했을때를 생각해보자. 스택이 거의 무한한 크기라고 가정해보더라도, 우리는

그저 pop을 한 번! 할 뿐이다. 그렇다면 이 역시

시간 복잡도는 O(1)로 나온다.

그렇다면 자료를 검색할때는 어떨까. 스택에 50개의 자료정보가 있을 때,

가장 최근의 자료를 검색한다면 우리는 위와 같은 상황이라 O(1)로 표현할 수 있지만,

가장 밑에 있는 자료가 필요하다고 가정한다면, 모든 자료를 찾아봐야하기 때문에 시간

복잡도는 O(n)이 된다.

++ 알고리즘 중 stack으로 풀 수 있는 문제가 나와서 같이 블로깅한다!

문제 설명

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

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

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

나의 풀이

function solution(ingredient) {
    let answer = 0
    const stack = []

 ingredient.forEach(el =>{
     stack.push(el)
     //stack배열에서 뒤에서부터 4개씩 자름
     if(stack.slice(-4).join('') === '1231'){
         //stack의 뒤에서부터 4개씩 자른 새로운 배열을 생성
         stack.splice(stack.length-4,4)
         answer++
     }
 })
   
    return answer
}