[Swift] suffix()로 인한 시간 초과 문제 해결하기

 

안녕하세요! 피피아노입니다 🎵

 

이번 포스팅에서는 프로그래머스에 있는 문제 중 하나인 "햄버거 만들기" 문제를 해결하는 과정에서 발생한 시간 초과 문제와 이를 해결한 방법에 대해서 작성하려고 합니다.

 

문제 링크는 아래에 남겨둘테니 참고하실 분들은 링크 참고 부탁드립니다.

햄버거 만들기 문제

 

문제 정의

햄버거 가게에서 재료가 순서대로 쌓일 때, 특정 패턴의 햄버거가 완성되면 이를 포장하고 제거하는 문제입니다.

 

일단 문제를 살펴보겠습니다.

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

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

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

제한사항:
1 ≤ ingredient의 길이 ≤ 1,000,000
ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

 

문제가 조금 긴데 핵심만 뽑아보면 아래처럼 정리할 수 있습니다.

• 재료가 아래에서부터 위로 쌓이고, 정해진 순서 [1, 2, 3, 1] (빵-야채-고기-빵)이 되면 하나의 햄버거로 인식하여 포장
• 포장한 햄버거는 스택에서 제거되고, 이후에도 쌓이는 재료로 다시 햄버거를 만듦
• 주어진 'ingredient' 배열은 재료가 쌓이는 순서를 나타내며, 상수가 포장한 햄버거의 총 개수를 return해야 함

초기 접근 방식

문제의 특성상 재료가 순서대로 쌓이고, 가장 최근에 쌓인 재료부터 확인하여 제거하는 방식이므로 Stack 자료구조를 활용하는 것이 적합하다고 판단하고 로직을 작성하였습니다.

구현 로직

1. 재료를 저장할 stack 배열을 선언
2. ingredient 배열의 각 재료를 순회하며 stack에 append
3. stack의 길이가 4 이상이 되면, 햄버거 완성 패턴([1, 2, 3, 1])과 일치하는지 확인
4. 패턴 일치 여부는 stack.suffix(4)를 통해 스택의 마지막 4개 요소를 가져와 비교
5. 패턴이 일치하면 stack.removeLast(4)를 통해 해당 재료들을 제거하고, 포장된 햄버거 개수를 나타내는 count 변수를 1 증가
6. count 변수를 return

func solution(_ ingredient:[Int]) -> Int {
    var stack: [Int] = []
    var count = 0
    for ingredient in ingredient {
        stack.append(ingredient)
        if stack.count >= 4 && stack.suffix(4) == [1, 2, 3, 1] {
            stack.removeLast(4)
            count += 1
        }
    }
    return count
}

 

이렇게 로직을 작성하고 테스트를 돌려보니 일부 테스트에서 시간 초과가 발생하였습니다.

원인 분석

문제의 원인은 Swift Array의 suffix(_:) 메서드 사용에 있었습니다. suffix(k)는 원본 배열의 마지막 k개 요소를 포함하는 ArraySlice를 반환합니다. ArraySlice는 원본 배열의 메모리를 공유하므로 데이터 복사가 발생하지 않아서 효율적이지만, ArraySlice 객체 자체의 생성 및 반환, 그리고 이 ArraySlice와 리터럴 배열 간의 비교 과정에서 미세한 오버헤드가 발생한다고 합니다.

 

이러한 오버헤드는 단인 연산에서는 무시할 수 있는 수준이지만, N이 1,000,000에 달하는 대규모 입력에서는 반복문 내에서 100만 번 가까이 호출되면서 누적되어 전체 실행 시간을 증가시킨다는 단점이 있었습니다. 즉, 0(N)이라는 점근적 복잡도는 유지되지만, 연산의 상수 시간이 커져서 시간 초과가 발생했던 것입니다.

최적화된 해결 방안

시간 초과 문제를 해결하기 위해 suffix() 메서드의 오버헤드를 줄이는 방향으로 코드를 개선했습니다.

 

ArraySlice를 생성하지 않고, 스택의 마지막 4개 요소를 직접 인덱스로 접근하여 비교하는 방식으로 변경하였습니다.

개선 로직

1. stack.suffix(4) == [1, 2, 3, 1] 대신, stack[stack.count - 4], stack[stack.count - 3], stack[stack.count - 2], stack[stack.count - 1]을 각각 [1, 2, 3, 1]의 해당 요소와 직접 비교합니다.
2. 햄버거 패턴 [1, 2, 3, 1]을 burgerPattern이라는 상수로 미리 정의하여 반복문 내에서 매번 배열을 생성하는 비용을 줄였습니다. (이 부분은 컴파일러 최적화에 따라 영향이 미미할 수 있으나, 명시적인 코드 가독성 및 잠재적 성능 향상을 위해 적용)

func solution(_ ingredient:[Int]) -> Int {
    var stack: [Int] = []
    var count = 0
    let burgerPattern = [1, 2, 3, 1] // 햄버거 패턴을 상수로 정의

    for item in ingredient {
        stack.append(item)
        
        if stack.count >= 4 {
            // ArraySlice 생성 없이 직접 인덱스 접근을 통한 비교
            if stack[stack.count - 4] == burgerPattern[0] &&
               stack[stack.count - 3] == burgerPattern[1] &&
               stack[stack.count - 2] == burgerPattern[2] &&
               stack[stack.count - 1] == burgerPattern[3] {
                
                stack.removeLast(4)
                count += 1
            }
        }
    }
    return count
}

 

이렇게 코드를 수정한 결과 모든 테스트 케이스를 성공적으로 통과하였습니다.

결론

초기에는 suffix()를 이용한 간결한 코드로 구현했지만, 미세한 오버헤드도 반복적으로 누적되면 성능 저하의 원인이 될 수 있음을 경험했습니다. 이를 해결하기 위해 ArraySlice를 생성하지 않고 인덱스로 직접 접근하는 방식으로 변경했고, 덕분에 모든 테스트 케이스를 효율적으로 통과할 수 있었습니다.

 

이 경험을 통해 아래 내용들에 대해서도 다시 한번 고민해볼 수 있었습니다.

• 시간 복잡도만큼이나 '연산의 상수 시간'도 중요
• 자잘한 성능 최적화라도 대규모 입력에서는 효과가 크다는 것을 체감
• 간단한 코드가 항상 효율적인 코드는 아님

---

감사합니다.

 

잘못된 내용이 있거나 더 좋은 내용 피드백은 언제나 환영합니다!

궁금하신 부분은 댓글로 질문 부탁드립니다!