본 캠프 40일차 TIL

오늘 배운 것
파이썬 문제풀이 접근법이 중요한 이유

 

공부하는데 사용한 문제

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

프로그래머스

내가 문제 풀이를 하려고 접근한 방식

def solution(ingredient):
    # 필요한 패턴
    burger_pattern = [1, 2, 3, 1]
    # 햄버거 카운터
    answer = 0
    
    # 재료 리스트를 순회하면서 검사
    while len(ingredient) >= 4:
        # 현재 리스트에서 패턴과 일치하는 부분 찾기
        found = False
        for i in range(len(ingredient) - 3):
            if ingredient[i:i+4] == burger_pattern:
                answer += 1
                # 패턴이 일치하는 부분을 제거하고 나머지 부분으로 리스트 재생성
                ingredient = ingredient[:i] + ingredient[i+4:]
                found = True
                break  # 첫 번째로 발견된 패턴 처리 후 다시 처음부터 탐색
        
        # 더 이상 패턴을 찾지 못하면 루프 종료
        if not found:
            break
    
    return answer

 

이 풀이법이 안 좋은 이유

1. 접근법이나 풀이를 하며 접근하는 것은 좋았지만 이 문제풀이를 할때 모든 요소를 다 챙기려고 하다보니 코드도 길어지고 코드의 복잡성도 늘어났다.
2. 리스트를 삭제하고 다시 재구성을 한뒤 검색을 다시 시작하는 행동에서 시간복잡도가 과하게 올라가 시간초과가 생겨버리는 경우가 많다.
3. 보다 효율적으로 리스트를 관리해야하고, 복잡성이 높아지지 않게 반복해서 리스트를 탐색하는 것이 아니라 패턴과 일치한 리스트의 내용을 즉각 삭제하여 시간 복잡성을 완화 할 필요성이 있다.

좋은 풀이법

def solution(ingredient):
    # 필요한 패턴
    burger_pattern = [1, 2, 3, 1]
    # 햄버거 카운터
    answer = 0
    
    check_list = []
    
    # 재료 리스트를 순회하면서 검사
    for item in ingredient:
        check_list.append(item)
        if check_list[-4:] == burger_pattern:
            answer += 1
            del check_list[-4:]
    
    return answer

 

이렇게 쉽고 간단하게 풀 수 있는 문제였다.

1. 이 방식은 ingredient 리스트를 한 번만 순회하므로 리스트를 재구성하고 다시 탐색하는 것보다 훨씬 효율적으로 바뀌었다.
2. check_list를 활용해서 최대 패턴 길이인 4개 요소만 검사하므로 메모리 사용이 효율적이고 직관적으로 문제를 해결 할 수 있다.
3. 단순하고 가독성이 좋아서 코드가 간결하고 이해하기 쉬워 유지보수가 용이하다.