[파이썬] 프로그래머스 햄버거 만들기 풀이

문제 확인

프로그래머스

나의 풀이

• 처음엔 str.replace(, , 1)를 활용해서 풀려고 했다.
• 이 경우 $O(N^2)$의 시간 복잡도를 가지기 때문에 시간 초과가 발생한다.

def solution(ingredient):
    answer = 0
    
    food = list(map(str, ingredient))
    food = "".join(food)
    while food:
    	# 한번에 1개의 문자열만 교체할 수 있도록 1을 설정 했다.
        temp = food.replace("1231", "", 1)
        if food == temp:
            break
        answer += 1
        food = temp
    return answer

• str.replace()으로 한번에 문자열을 교체할 수 있도록 코드를 수정했다.
• 하지만 이번엔 테스트 케이스를 통과하지 못 했다.
• 문제에서 한번에 1 개의 문자열만 교체한다고 했기 때문에, 테스트 케이스도 이와 관련 있을 것이라고 생각한다. 
  • 아쉽게도 지금은 반례가 생각나지 않는다.

# 따로 옮겨 포장한다고 돼 있음 -> 한번에 1개만 가능 -> 테스트 케이스도 이와 관련 있을 것...
def solution(ingredient):
    answer = 0
    
    food = list(map(str, ingredient))
    food = "".join(food)
    while food:
        temp = food.replace("1231", "")
        if food == temp:
            break
        # 포장한 햄버거 개수
        answer += (len(food) - len(temp)) // 4
        food = temp
    return answer

• 최종 풀이
  • Stack 개념을 활용해서 풀었다.

def solution(ingredient):
    answer = 0
    # stack 활용
    food = []
    for i in ingredient:
        food.append(i)
        if food[-4:] == [1, 2, 3, 1]:
            answer += 1
            for _ in range(4):
                food.pop()
    return answer