[Lv.1] 햄버거 만들기 [프로그래머스_코딩테스트] [스택, 슬라이딩윈도우]

🔍 문제 요약

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

프로그래머스

해당 문제는 햄버거를 재료순서대로 쌓아서 완성된 개수를 구하는 문제로 int배열(재료들 순서)이 주어진다.

 

🧠 나의 접근 방식과 시행착오

스택 문제로 바로 파악하고 스택으로 접근하려고 했던 거에서 실수를 한 듯 하다. 스택을 사용하게 되면 push, peek, pop에 집중을 하게 되는데 이런 경우 순서가 중요한 상태로 쌓였을 때 이전에 쌓인 것들을 가져와서 비교하는 부분에서 자연스럽게 막히게 되는 듯 하다. 이전에 푼 문제에서 슬라이딩 윈도우 방식이 있었는데 그 과정을 생각을 못했었다. 그래서 이걸 스택을 넣으면서 이전 것들도 다 가지고 있게 하려니 List<Stack<int>> ? 까지 생각을 하게 되면서 더 복잡해진 케이스.. 아래의 필자가 중간에 멈춘 코드를 올려둔다.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 햄버거 만들기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/133502
    /// </summary>
    public int solution(int[] ingredient)
    {
        // 완성된 버거의 개수
        int burgerCount = 0;
        
        // 햄버거 조립 순서 (빵 - 야채 - 고기 - 빵)
        int[] ingredientOrder = {1, 2, 3, 1};
        int ingredientIndex = 0;
        
        // 조립
        var ingredientStack = new List<Stack<int>>();
        int stackIndex = 0;
        ingredientStack.Add(new Stack<int>());

        foreach (var value in ingredient)
        {
            ingredientStack[stackIndex].Push(value);

            if (ingredientStack[stackIndex].Peek() == ingredientOrder[ingredientIndex])
            {
                // 버거 완성
                if (ingredientIndex == ingredientOrder.Length - 1)
                {
                    burgerCount++;
                    stackIndex--;
                    ingredientIndex = 0;
                    continue;
                }
                
                ingredientIndex++;
            }
            else
            {
                ingredientStack.Add(new Stack<int>());
                stackIndex++;
            }
        }

        // 버거에 남아 있는 것들
        if (ingredientStack.Count > 0)
        {
            
        }
        
        return burgerCount;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int[] ingredient1 = { 2, 1, 1, 2, 3, 1, 2, 3, 1 };
        int[] ingredient2 = { 1, 3, 2, 1, 2, 1, 3, 1, 2 };
        Console.WriteLine(sl.solution(ingredient1));
        Console.WriteLine(sl.solution(ingredient2));
    }
}

 

✅ 풀이 코드

슬라이딩 윈도우와 list를 써서 가장 마지막에서 4개의 데이터를 비교해서 (슬라이딩 윈도우) RemoveRange하게 지우면서 작동한다. 아래에 풀이 과정을 올려둠. 실제로는 정말 단순한 코드이나 스택에 집착한 상태로는 풀이가 복잡해지거나 어려웠지 않을까 싶다.

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int[] ingredient)
    {
        int burgerCount = 0;
        var stack = new List<int>();

        foreach (var ing in ingredient)
        {
            stack.Add(ing);

            if (stack.Count >= 4)
            {
                int count = stack.Count;
                if (stack[count - 4] == 1 &&
                    stack[count - 3] == 2 &&
                    stack[count - 2] == 3 &&
                    stack[count - 1] == 1)
                {
                    // 햄버거 완성 → 재료 제거
                    stack.RemoveRange(count - 4, 4);
                    burgerCount++;
                }
            }
        }

        return burgerCount;
    }
}

 

🔄 정리

스택이라는 구조에 너무 몰입해서 문제를 보려니 실제론 간단한 리스트로 작업을 풀 수 있는 것도 이렇게 틀리게 되는 듯 하다. 문제의 순서 비교가 중요한 케이스에서는 리스트와 슬라이딩 윈도우 구조를 잘 활용해서 접근하는 것이 좋겠다.

 

핵심 포인트

 

문제 풀이에 도움이 되는 체크리스트