[프로그래머스 / C언어] 햄버거 만들기

프로그래머스 코딩테스트 연습 문제인, 햄버거 만들기 문제를 풀어보았습니다.

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

프로그래머스

 

stack의 개념을 알고 있으면 쉽게 풀 수 있는 문제입니다. 다만, c언어에는 스택이 구현되어 있지 않기 때문에, 저는 그냥 top 변수 하나와 일반 int 배열을 활용하여 스택처럼 활용해주었습니다. 이 문제는 문제에서 힌트를 얻으면 더 쉽게 접근이 가능한 문제입니다. 문제에서 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다.  라고 언급하고 있습니다. 따라서, 저는 이 흐름을 그대로 따라, stack에 재료들을 쌓아나가다가, 재료가 3개 이상 쌓인 상태에서 1(빵)을 마주했을 때, 앞 3개의 재료가 차례로 고기 - 야채 - 빵인지 확인하고, 맞다면 top을 사용된 빵 하나 전으로 다시 설정하여, 다시 같은 과정을 반복하는 방법이었습니다. 

 

제가 쓴 코드에서 유의해서 볼 점은, 재료가 3개 이상 쌓인 상태에서 1(빵)을 마주했을 때, 이를 스택에 넣지 않고, 스택의 top부터 세개의 재료만 순회하여 햄버거를 만들 수 있는지 확인한다는 점입니다. 이 때 햄버거를 만들 수 있다면, answer(만들 수 있는 햄버거의 개수)에 1을 더해주고 나서, 그 빵은 다시 사용할 수 없기 때문에, 아래 stack에 현재 순회 중인 재료를 넣는 코드를 실행하지 않도록 반드시 continue문을 사용해주어야 합니다. 하지만 햄버거를 만들 수 없는 경우(res == false인 경우)에 그 빵을 사용해 햄버거가 만들어지지 않았다는 뜻이므로, 그 빵을 만드시 stack에 넣어주어야 합니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int ingredient[], size_t ingredient_len) {
    int answer = 0;
    int pre = 0;
    
    int *stack = (int*)malloc(sizeof(int) * ingredient_len);
    int top = -1;
    for (int i = 0; i < ingredient_len; i++) {
        if (top >= 2 && ingredient[i] == 1) {
            bool res = true;
            for (int i = 0; i < 3; i++) {
                if (stack[top-i] != 3 - i) res = false;
            }
            if (res) {
                top -= 3;
                answer++;
                continue;
            }
        }
        stack[++top] = ingredient[i];
    }
    free(stack);
    return answer;
}