50. 햄버거 만들기 ★

유형: 구현

풀이 시간 : 20분

 

1. 시간 초과 발생. 

def solution(ingredient):
    answer = 0
    i = 0
    while ingredient:
        if i > len(ingredient) - 3: 
            break
        if ingredient[i:i+4] == [1, 2, 3, 1]:
            del ingredient[i:i+4]
            answer += 1
            i = 0
        else:
            i += 1
    return answer

 

ingredient에 일치하는 부분을 발견한 뒤 i=0부터 다시 탐색하는 부분이 문제였던 것 같다.

다시 작성해보자. 

 

2. 정답 코드

def solution(ingredient):
    answer = 0
    i = 0
    while ingredient:
        if i > len(ingredient) - 3: 
            break
        if ingredient[i:i+4] == [1, 2, 3, 1]:
            del ingredient[i:i+4]
            answer += 1
            if i > 3:
                i -= 3
            else:
                i = 0
        else:
            i += 1
    return answer

 

- 종료 조건 : i가 len(ingredient) - 3보다 클 경우 => 체크끝, 반환

- 만약 ingredient[i:i+4] == [1, 2, 3, 1] 라면 포장

  => 이 부분을 ingredient에서 제거

  => answer에 +1

  * index update : 3칸 앞에서부터 새로 체크하면 된다. (그 앞부분은 삭제의 영향을 받지 않으므로, 체크할 필요가 없다.)

- ingredient를 찾지 못했다면 다음 index 탐색 

 

깔끔하게 동작한다.