[programmers] lv.1 햄버거 만들기(unsolved>solved)

jeongjeong2·2023년 1월 22일

For coding test

목록 보기

17/59

문제 설명 문제 바로가기

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

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

제한사항

1 ≤ ingredient의 길이 ≤ 1,000,000
ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

입출력 예

문제 접근

풀이 시간 10~15분 정도

list를 string형으로 바꾼 후 문자열 내에서 '1231'에 해당하는 부분 공백으로 replace

기존의 length와 tuning 후의 문자열 length를 비교해서 answer값 return

나의 풀이 (unsolved)

def solution(ingredient):
    str_ingredient = ''.join(list(map(str,ingredient)))
    while True:
        if len(str_ingredient) == len(str_ingredient.replace('1231','')):
            return (len(ingredient)-len(str_ingredient))/4
        str_ingredient = str_ingredient.replace('1231','')

풀이 반례

한 번에 1231이라는 문자열을 replace하면 123'1'에 사용될 1이 후의 '1'231에 먼저 사용되면서 순서가 엉키게 된다.
이런 경우를 대비하여 stack으로 푸는 것이 바람직하다.
(stack으로 풀지 않으면 list길이가 길 때 for문 내에서 replace하는 동안 계속 n번의 실행이 반복되기 때문에 n^2의 시간 복잡도를 갖게 된다.

나의 풀이(solved)

def solution(ingredient):
    answer = []
    for i in ingredient: 
        answer.append(i)
        if answer[-4:] == [1,2,3,1]:
            for j in range(4):
                answer.pop()
    return (len(ingredient) - len(answer)) /4
for문 내에서 replace를 쓰는 것 자체가 n^2의 시간복잡도를 가지게 된다.

slicing을 이용해서 list내의 범위가 내가 제시한 범위와 같아지는 것을 조건으로 쓰는 것도 가능하다!

pop()자체는 가장 마지막에서 빼는 것이라 복잡도가 1이지만 index를 지정해주는 순간 그 index만큼 늘어난다 ex)pop(0)는 마지막에서 index가 0인 element까지 이동해야하므로 n만큼의 시간복잡도를 가진다.

다른 사람 풀이 (후첨)

def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            for i in range(4):
                s.pop()
    return cnt