[프로그래머스] Swift - 햄버거 만들기(LV.1)

👆문제풀러 가기👆

문제 설명

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

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

---

풀이 [ 메모리: 63,897kb, 최대시간: 597.60ms ] 

func solution2(_ ingredient:[Int]) -> Int {
    var stack = [Int]()
    let recipe = [1, 2, 3, 1]
    var result = 0

    for i in ingredient {
        stack.append(i)

        if Array(stack.suffix(4)) == recipe {
            stack.removeLast(4)
            result += 1
        }
    }
    return result
}

단순한 스택 문제이므로, LIFO(Last In First Out)을 지켜주면 된다. 

1. stack배열을 생성해주고, stack배열에 각각의 재료로 햄버거 재료(ingredient)를 삽입한다.
2. stack의 마지막 4개의 재료가 햄버거 재료와 같을 때, 햄버거를 만든다.(removeLast(4))
3. 그리고 햄버거의 갯수를 증가시킨다.

---

ArraySlice에 대한 짧은 정리

단순한 문제이지만, ArraySlice에 대해 공부할 이유가 되었던 문제였다.

stack.suffix(4)를 사용해 생성된 배열은, ArraySlice타입으로 사실 배열이 생성되는 게 아니라 기존 Array와 참조관계에 있다.

ArraySlice를 변경하면 원본 Array에도 영향을 준다고 하여, 강한 참조 관계로 추정되는데,

이런 참조관계에 있을 때에는 Heap영역을 사용하기 때문에 상대적으로 속도가 느려지는 문제가 생긴다.

또한 강한 참조를 유지하기에 Memory Leak이 발생할 여지가 농후하다.

 

따라서 ArraySlice타입을 사용할거라면, 완전히 별개의 값으로 만들어 강한 참조 사이클을 해제해줄 필요성이 있다는 걸 알게되었다.

 

참고자료

1. 애플 공식문서
2. Wireframe - (Swift) Array 완전 정복  -04.ArraySlice
3. Zeddios - Swift) Contiguous Array / ArraySlice

사실 모두 같은 내용을 다루고 있지만 나름 각각의 장점이 있는 블로그라서 함께 올려봤다.

---

알게 된 이유

이 사실을 알게 된 배경에는, 문제를 풀었을 때 최초 풀이에서는 최대 소요시간이 7000ms까지 올랐다가

stack.suffix(4)에 Array를 감싸니 597.60ms로 줄어들었기 때문이다.

물론 1,000,000자리 길이의 배열에 대한 연산이기 때문에 평소에는 큰 차이를 주지는 않을테니, 연산속도보다는 강한참조로 묶여 반드시 ArraySlice가 먼저 종료되도록 설계해야한다는 점과 서로 간의 영향을 주고 있다는 점 등을 알아두면 좋을 것 같다.

 

추후 ArraySlice와 클래스, 구조체에 대한 내용을 정리해둬야겠다.