[Python] 프로그래머스 코딩테스트 연습 > 햄버거 만들기

안녕하세요! 오늘은 햄버거 만들기 문제 풀이를 통해 사고 과정에 따라 코드를 하나씩 추가해가면서 핵심 문제인 시간 초과를 해결해 보겠습니다.

 

프로그래머스 문제 링크

프로그래머스

 

모든 문제의 저작권은 프로그래머스에게 있음을 밝힙니다.

---

목차

 

1. 문제 설명
2. 풀이 과정

---

 1. 문제 설명

 

 

간단하게 설명하면 1, 2, 3으로 조합된 list인 ingredient를 parameter로 받아서 [1, 2, 3, 1] 순서의 햄버거가 몇 개나 만들어지는지 return 하는 함수를 작성하면 됩니다.

 

---

2. 풀이 과정

 

• 햄버거 찾아내기 (리스트 탐색)

 

def solution(ingredient):
    answer = 0

    for idx in range(0, len(ingredient)-3):                   
        if ingredient[idx:idx+4] == [1,2,3,1]:
            del ingredient[idx:idx+4]
            answer += 1
    
    return answer

 

for문을 통해 리스트를 탐색하면서 슬라이싱을 통해 [1, 2, 3, 1]인 구간을 찾아냅니다.

조건을 충족할 경우 그 구간은 삭제하고 return값에 1을 더합니다.

하지만 이대로 실행하면 그다음 햄버거를 찾을 때 index 초기화가 되지 않기 때문에 반복문이

추가적으로 필요합니다.

 

• While문 탈출 조건 추가

 

def solution(ingredient):
    answer = 0
    len_check = []

    while len(set(len_check)) == len(len_check):
        for idx in range(0, len(ingredient)-3):                   
            if ingredient[idx:idx+4] == [1,2,3,1]:
                del ingredient[idx:idx+4]
                answer += 1
                break
    
        len_check.append(len(ingredient))
    
    return answer

 

우선 for문 내에 햄버거가 만들어지면 반복문을 중단하는 break를 추가해 주었습니다.

len_check이라는 빈 list를 생성해주고 while문이 반복될 때마다 len(ingredient)를 append해 줍니다.

이때 중복인 element가 있는 경우 즉, 햄버거가 만들어지지 않은 경우를 set(ingredient)와 원본 ingredient의 길이 비교를 통해 탈출 조건을 걸었습니다.

하지만 이대로 실행할 경우 for문의 idx가 0부터 시작하기 때문에 불필요한 탐색이 일어납니다. 이 때문에 ingredient의 길이가 긴 경우 시간초과가 발생하게 됩니다.

 

• 불필요한 탐색 줄이기 (최종 코드)

 

def solution(ingredient):
    answer = 0
    len_check = []
    idx_check = 2

    while len(set(len_check)) == len(len_check):
        for idx in range(idx_check-2 ,len(ingredient)-3):                   
            if ingredient[idx:idx+4] == [1,2,3,1]:
                del ingredient[idx:idx+4]
                answer += 1
                idx_check = idx
                break
    
        len_check.append(len(ingredient))
    
    return answer

 

for문의 시작 index를 햄버거가 만들어진 시점의 idx -2로 설정합니다. 또한 idx를 확인하는 idx_check 변수를 선언하고 맨 처음 for문 돌 때를 대비하여 초기 값을 2로 설정합니다.

ingredient가 [1, 1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]라고 가정해 보겠습니다.

[1, 1, 1, 1, 2, (1, 2, 3, 1), 3, 1, 2] 이렇게 햄버거가 만들어지고 이때 시작 idx는 5입니다.

[1, 1, 1, 1, 2, 3, 1, 2]가 남게 되고 idx -2인 3부터 탐색하면 됩니다. 

idx - 2 이전에서는 절대 햄버거가 만들어질 수 없습니다. 왜냐하면 최악의 경우를 생각해 보아도

(1, 2, 3, 1) 앞에 1, 2, 3이 있으면 (1, 2, 3, 1), 2, 3 ,1 이런 식으로 앞에서 먼저 햄버거가 만들어지기 때문에 굳이 idx - 2 이전의 경우는 탐색할 필요가 없습니다.

 

 

더 좋은 풀이가 많이 있지만 제가 고민했던 과정들을 통해 배울만한 내용이 있을 것이라고 생각합니다. 도움이 되셨다면 하트와 구독 부탁드립니다.