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

 

문제

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

프로그래머스

 

 

 

풀이

처음에 생각한 문제풀이는 다음과 같다.

 

"상수가 만들 수 있는 햄버거가 "1234" 이니까 ingrdient가 [2,1,1...]으로 들어오면 이걸 문자열로 바꾸고 python replace()을 통해서 "" 으로 바꿔서 count 처리하면 쉽게 풀리겠다"

 

그렇게 해서 문제를 풀었다. 

 

from typing import List

def solution(ingredient: List[int]):
    
    ingrdient: str = "".join(list(map(str, ingredient)))
    count: int = 0
    
    while ingrdient.count('1231') != 0:
        ingrdient = ingrdient.replace('1231', "", 1)
        count += 1
      
    return count

 

 

결과는 몇 개의 케이스에서 시간 초과를 맛보았다 아마 while 문 처리하면서 replace 하는 것이 시간을 많이 잡아먹는 모양이었다. 따라서 List을 이용하여 순차적으로 들어오는 것을 받아 처리하여 문제를 풀어야겠다고 생각했다. 

 

 

from typing import List

def solution(ingredient: List[int]):
    
    case: List[int] = []
    count: int = 0
    
    for i in ingredient:
        case.append(i)
        if case[-4:] == [1, 2, 3, 1]:
            case = case[:-4]
            count += 1
            
    return count

 

 

 

하지만 이번에도 시간초과를 맞았다. case [-4:] 이 부분이 O(N)인데, if 문 사이에 걸쳐서 작성되어 총 시간 복잡도가 O(N ^ 3) 이 나와서 초과된 듯하다 그래서 case [:4] 부분을 for _ in range(4): list.pop()으로 바꾸어 제출하였다. 

 

from typing import List

def solution(ingredient: List[int]):
    
    case: List[int] = []
    count: int = 0
    
    for i in ingredient:
        case.append(i)
        if case[-4:] == [1, 2, 3, 1]:
            for _ in range(4):
                case.pop()
            count += 1
            
    return count

 

List slice을 할 때, O(N) 이 든다는 사실을 인지하고 if, for 문을 사용할 때 복잡도를 고려하여 사용하여야겠다.