[프로그래머스] 햄버거 만들기

문제 링크

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

문제 설명

• 재료가 들어오는 순서가 주어졌을 때 연속되는 빵,야채,고기,빵 순서로 들어왔을 때 바로 햄버거 만들어버림.
• 만들 수 있는 햄버거 갯수 반환하라
• 자세한 설명은 링크에서 확인하시라...

1차 시도

def solution(ingredient):
    ing = "".join(str(i) for i in ingredient)
    l = len(ing)
    result = 0
    while '1231' in ing:
        ing = ing.replace('1231','',1)
        result+=1
    return result

replace로 간단하게 해결해보려고 했으나 간단하지 않았다.
ingredient 길이가 최대 1,000,000이므로 (얘 만들다가 죽는거 아닌가) 시간초과로 실패!

2차 시도

def solution(ingredient):
    ing = "".join(str(i) for i in ingredient)
    l = len(ing)
    while '1231' in ing:
        ing = ing.replace('1231','')
    return (l-len(ing))//4

그러면 replace에 count 제한을 두지 않고 쓰고 만드는 햄버거 갯수를 따로 계산해주면 시간을 줄일 수 있지 않을까? 했지만 이렇게 하면 순서대로 재료가 들어와 조건을 충족했을 때 바로바로 만드는 상황을 가정하지 못하므로 실패!

3차 시도

def solution(ingredient):
    stack = []
    for i in ingredient:
        stack.append(i)
        if stack[-4:]==[1,2,3,1]:
            stack = stack[:-4]
    return (len(ingredient)-len(stack))//4

뭔가 문제가 스택스러우니 스택을 이용해보자! 해서 해봤는데 케이스 2개가 시간 초과였다..!

아니 그래서 이거 뭐지? 시간초과가 나면 이 방법 자체가 틀린건가? 근데 뭔 방법이 더 있는지 모르겠는데? 하고 질문들을 살펴보니,,, 나랑 같은 케이스에서 시간초과가 난 사람이 있었다.
알고보니 슬라이싱이 시간이 오래걸린다는 것...!
그래서 이를 수정해주니까

4차 시도 - 통과

def solution(ingredient):
    stack = []
    for i in ingredient:
        stack.append(i)
        if stack[-4:]==[1,2,3,1]:
            for _ in range(4):
                stack.pop()
    return (len(ingredient)-len(stack))//4

슬라이싱 대신 pop을 사용했다.
아니 pop을 4번 하는게 슬라이싱보다 적게 걸린다니
아마 stack의 크기가 큰 경우 그런 상황이 발생하는 것 같다.
즉 pop을 이용하면 시간복잡도 O(4)를 갖는데, 슬라이싱을 이용하면 O(length-4)만큼 걸리므로 stack이 커질수록 시간이 오래 걸린다.
슬라이싱에 O(b-a)의 시간복잡도가 걸리는 것은 꼭 기억해두자.

와 이건 좀 많이 놀라워서 꼭 기록해두자고 생각했다.

혹시 슬라이싱을 사용했는데 시간초과가 뜬다면 슬라이싱을 의심해보자.

정리

• 슬라이싱: list[b:a]의 슬라이싱은 O(b-a)의 시간복잡도를 갖는다. stack 사용시엔 pop을 잘 이용해보자.
• list to str: str의 join 함수를 이용하자. "".join(list)와같이 사용한다면 list의 원소들을 공백 없이 이어준다. 만약 list에 int 값이 들어있다면 오류가 발생하니, 이 경우엔 map 혹은 comprehension을 사용해주자.