1월 27일 TIL

프로그래머스 코딩테스트 [ 햄버거 만들기 ]

Github 링크

• 이 문제는 주어진 재료 순서가 있다고 하고, 주어진 재료 순서를 쌓고, 빵-야채-고기-빵 순서가 되면 햄버거를 하나 만들고, 다시 재료를 쌓고 계속 반복해서, 만들 수 있는 햄버거의 최대 개수를 찾는 것이다.
• 문제를 잘보면 애초에 쌓는거라고 힌트를 줬는데도, 처음에는 이 문제를 Stack으로 풀 생각을 안했다. 단순히 Array에서 [1,2,3,1]를 찾고 해당 subArray를 원래 Array에서 지우고, 다시 [1,2,3,1]를 찾는 방식으로 진행했는데, 당연히 이러다 보면 시간 복잡도가 굉장히 높기 때문에, 시간 초과 오류가 떴다.
• 그래서 Stack을 사용해서 문제를 풀 방법을 생각했다. 문제 그대로 재료를 Stack에 순서대로 push 하고, stack의 위 4개의 요소가 [1,2,3,1]이 되면 pull 하는 방법이다.
• 우선 내가 처음으로 풀었던 방법이다.

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

• stack에 재료가 들어올때 마다 추가해주고, stack.suffix(4) == receipt인지 확인하고, 맞으면 removeLast(4)로 삭제해주고, ans +=1. 그래서 제출을 해봤더니 시간초과 오류가 떴다. 잉? 이렇게 해도 시간초과가 뜬다고? 그래서 다른 분이 풀었던걸 참고를 해봤는데, suffix 대신 index로 접근했다. 이렇게하면 오류가 안떠서 프로그래머스 제출된 다른사람의 풀이를 봤는데. 아래코드와 같다.

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

• ??? 무슨 차이가 있는거지. 그래서 혹시나 suffix 변수를 만들면 type이 달라지나 확인해봤는데, 변수를 만들나 안만들나 ArraySlice type을 갖게 된다. 그래서 이게 뭐지 싶었는데, 더 신기한건 if Array(stack.suffix(4) == receipt 로 하면 또 시간초과가 안뜬다.
• 내가 생각하기에는 정확하는 답은 찾지를 못해서 추측을 해보자면, stack.suffix(4)로 바로 비교하면, ArraySlice == Array로 비교하는거라서 문제가 생기는게 아닐까 생각이 든다, let suffix = stack.suffix 로 선언을 하면 우선적으로 ArraySlice으로 타입 추론이 되는거지만, if문에서 비교를 할때 Array로 타입 추론이 자동으로 바껴서 문제가 생기지 않는 반면에, Stack.suffix == Array 하면 매번 Stack.suffix를 타입 추론하는데서 시간초과가 뜨는게 아닌가 싶다. 그 근거로는 let suffix: ArraySlice = stack.suffx(4) 하고, if suffix == receipt 하면 오류가 뜬다. 즉 swift자체에서 타입추론을 하고 있었다는 의미인데, 그 타입 추론과정에서 시간이 더 많이 소요되서 그런것 같다.