[프로그래머스][PYTHON] Lv. 1 햄버거 만들기
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/133502
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
내 풀이 (오답)
처음에는 주어진 리스트를 문자열로 바꿔서, 햄버거를 만들 수 있는 문자를 제거하려 했다.
# 빵 – 야채 – 고기 - 빵 (1, 2, 3 -> 빵, 야채, 고기)
def solution(ingredient):
answer = 0
# 햄버거를 만드는 순서는 1 -> 2 -> 3 -> 1
ham = '1231'
# 주어진 리스트를 string으로 변경([2, 1, 1] -> '211')
ingredient = list(map(str, ingredient))
ingredient = ''.join(ingredient)
# 문자열에서 '1231'을 찾을 수 있으면..
while ingredient.find(ham) > 0:
# 1231을 제거 -> 더 이상 찾을 수 없을 때까지 반복
ingredient = ingredient.replace(ham, '')
answer += 1
return answer
이 풀이의 경우 예제 케이스에 대해서는 정답이 나지만, 실제 테스트 케이스에 대해서는 22점 밖에 나오지 않는다.
1. ingredient 배열을 문자열로 변환하는 부분의 시간 복잡도 = O(n)
ingredient = list(map(str, ingredient))
ingredient = ''.join(ingredient)
2. 문자열에서 '1231'을 찾는 부분의 시간 복잡도 = O(n^2)
while ingredient.find(ham) > 0:
ingredient = ingredient.replace(ham, '')
answer += 1
이 부분에서 find() 메서드는 최악의 경우 O(n)의 시간 복잡도를 가진다.
또한, replace() 메서드 역시 최악의 경우 O(n)의 시간 복잡도를 가진다.
이를 루프 내에서 반복하기 때문에 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다.
다른 사람 풀이 (정답)
마땅한 방법이 떠오르지 않아 다른 사람의 풀이를 보고 해결해보았다.
아래는 스택을 이용하여 각 재료를 순차적으로 처리하는 풀이이다.
def solution(ingredient):
stack = []
answer = 0
for i in ingredient:
stack.append(i)
if stack[-4:] == [1,2,3,1]:
answer += 1
del stack[-4:]
return answer
먼저, 햄버거의 속 재료가 쌓이는 것처럼 각 재료를 스택에 하나씩 추가한다.
이러한 스택의 마지막 4개 요소가 햄버거를 만들 수 있는 배열 [1, 2, 3, 1]과 같으면,
del 함수를 이용해 이 요소를 제거한다.
스택에 원소를 추가할 때 시간 복잡도는 O(1)이며,
del을 이용해 원소를 제거하는 시간 복잡도 역시 O(1)이다.
동일한 방법이지만, pop()을 사용할 수도 있다.
def solution(ingredient):
answer = 0
stack=[]
for i in ingredient:
stack.append(i)
if stack[-4:]==[1,2,3,1]:
answer+=1
for k in range(4):
stack.pop()
return answer
시간 복잡도 정리
Python 자료형별 시간 복잡도 정리
본격적으로 코딩 테스트를 준비하면서, 자료형별 연산자의 시간복잡도에 관심을 가지게 되었다.특시 백준에서 알고리즘 문제를 풀다보면 '시간 초과'문제를 자주 겪게 되는데, 어떤 함수가 얼
velog.io
시간 복잡도에 대한 설명을 자세히 정리해둔 블로그가 있어 함께 남겨본다!