프로그래머스-햄버거 만들기(파이썬, python)

SA Jung·2022년 10월 28일
0

Programmers 문제 풀이

목록 보기
13/14
post-thumbnail

[문제링크]

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

[github 링크]

https://github.com/JungSangA/Algorithm_Study/blob/main/%EB%B0%B0%EC%97%B4/%ED%96%84%EB%B2%84%EA%B1%B0%20%EB%A7%8C%EB%93%A4%EA%B8%B0.ipynb

1. list 인덱싱을 통한 풀이

from collections import deque

def solution(ingredient):
    ingredient = deque(ingredient)
    burger = []
    answer = 0
    
    while ingredient:
        burger.append(ingredient.popleft())
        if burger[-4:] == [1,2,3,1]:
            burger = burger[:-4]
            answer+=1
            
    return answer
  • burger의 조건을 판별하고, 남은 burger의 재료를 burger[:-4]를 통해 인덱싱한다.
  • 시간초과가 뜨고 다른 테스트케이스도 겨우겨우 합격한 것 같다.

2. pop()을 통한 list제거

from collections import deque

def solution(ingredient):
    ingredient = deque(ingredient)
    burger = []
    answer = 0
    
    while ingredient:
        burger.append(ingredient.popleft())
        if burger[-4:] == [1,2,3,1]:
            for _ in range(4):
                burger.pop()
            answer+=1        
    return answer
  • 인덱싱을 하지않고, pop()을 통해 4개만큼 제거해주면서 시간복잡도를 줄이는 알고리즘을 구현했다.
  • 확실히 속도 개선이 있었고 통과를 했다.

3. deque를 쓰지 않고, for문으로 단순 코딩

def solution(ingredient):
    burger = []
    answer = 0
    for i in ingredient:
        answer.append(i)
        if burger[-4:] == [1, 2, 3, 1]:
            answer += 1
            for _ in range(4):
                burger.pop()
    return answer
  • deque를 이용하지 않고, 단순 for문으로 1개씩 꺼내어 접근하는 알고리즘과 동일하다고 판단하여 속도개선을 위해 알고리즘을 구현해봤다.
  • 확실히 for문으로 1개의 요소씩 꺼내어 진행하다보니 시간복잡도가 더 개선되었다.
  • 복잡한 알고리즘 문제가 아니었으므로 deque까지는 쓸 필요가 없었나 보다.
profile
Tomorrow will be better than yesterday :)

0개의 댓글