[Programmers] 햄버거 만들기 - 133502

시간 초과로 stack 이용해서 O(n)로 풀기.

 

Question

 

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

 

 

Code : Time Complexity O(n)

 

def solution(ingredient):
    answer = 0
    stack = []
    
    for i in ingredient: # O(n)
        stack.append(i) # O(1)
        if stack[-4:] == [1,2,3,1] : answer += 1; del stack[-4:] # O(1)
    
    return answer

 

 

Code 2 : Time Complexity O(n^2)

 

def solution(ingredient):
    answer = 0
    hamberger = "1231"
    str_ing = ''.join(map(str,ingredient))
    
    while hamberger in str_ing : # in O(n)
        answer += 1
        str_ing = str_ing.replace(hamberger,'',1) # O(n)
            
	return answer

 

now me

On my github