코딩테스트 연습 문제: 햄버거 만들기
문제 분석
햄버거를 만드는 문제이다.
정해진 순서 빵 - 야채 - 고기 - 빵 순으로 포장하게 되며 재료는 아래서부터 위로 쌓이게 된다.
여기서 여섯 번째 재료가 쌓였을 때 3, 4, 5, 6 재료를 이용하여 햄버거를 포장한다고 하고,
아홉 번째 재료가 쌓였을 때 2, 7, 8, 9 재료를 사용하여 포장한다고 한다.
빵 야채 고기를 순서대로 1, 2, 3으로 한다.
burger = { '빵': 1, '야채': 2, '고기': 3}
제한사항 및 입출력
N의 범위가 1 ~ 1,000,000으로 주어졌으니 시간 복잡도는 최소 O(N) ~ 최대 O(logN)까지로 제한된다.
문제 풀이
일단 처음 봤을때
'그러면 i부터 i+3까지 X같은 값으로 바꿔서 연산을 건너 뛰거나 pop을 이용해서 하면 되지 않을까?'
라고 생각하며 코드를 작성했었다.
makeCount = 0 for i in range(len(ingredient)): if ingredient[i] == 1 and ingredient[i+1] == 2 and ingredient[i+2] == 3 and ingredient[i+3] == 1: makeCount += 1 ingredient.pop(i) ingredient.pop(i+1) ingredient.pop(i+2) ingredient.pop(i+3) i = 0 continue if len(ingredient) < 3: break
순서대로 1, 2, 3, 1이 되면 makeCount를 증가시키고, 리스트에서 인덱스에 해당하는 값을 pop시키고 i를 0부터 다시 시작해 for문을 반복하도록 했는데...
IndexError: list index out of range
리스트의 인덱스가 범위를 벗어났다고 에러가 발생한다.
어떻게 할까 하다가 연속된다면 한번에 비교하도록 했다.
for i in range(len(ingredient)): if ingredient[i:i+4] == [1,2,3,1]: makeCount += 1파이썬 최고...
여튼 저렇게 한번에 비교할 수 있는데 해당 if문을 통과한다면 makeCount += 1을 하도록 했다.
그럼 makeCount가 올라갔으면 해당 원소는 리스트에서 지워야 하는데 pop을 써보니 결과가 달랐다.
ingredient.pop(i) print(i, ingredient) ingredient.pop(i+1) print(i+1, ingredient) ingredient.pop(i+2) print(i+2, ingredient) ingredient.pop(i+3) print(i+3, ingredient)
하나씩 다 찍으면서 확인을 해보았더니
2 [2, 1, 2, 3, 1, 2, 3, 1]
3 [2, 1, 2, 1, 2, 3, 1]
4 [2, 1, 2, 1, 3, 1]
5 [2, 1, 2, 1, 3]
처럼 나왔는데 pop이 뺀 자리를 한 자리씩 땡김에도 불구하고 인덱스값을 계속 늘려서 발생한 문제였다.
여기서는 i값을 일정하게 한다면 원하는 결과가 나오기는 한다.
2 [2, 1, 2, 3, 1, 2, 3, 1]
3 [2, 1, 3, 1, 2, 3, 1]
4 [2, 1, 1, 2, 3, 1]
5 [2, 1, 2, 3, 1]
이제 for문을 반복하도록 i값을 바꾸는 일만 남았는데 이것보다 더 쉬운방법은 while문을 사용하여 ingredient 값이 조합하는 최소 갯수인 4보다 적을 경우까지 돌리면 된다.
While
def solution(ingredient): makeCount = 0 i = 0 while i < len(ingredient) - 3: if ingredient[i:i+4] == [1,2,3,1]: makeCount += 1 ingredient.pop(i) ingredient.pop(i) ingredient.pop(i) ingredient.pop(i) i = 0 else: i += 1 return makeCount
코드 분석
while i < len(ingredient) - 3:
리스트의 끝까지 돌면서 -3을 해준다면 최소 갯수인 4를 만족하지 못하기 때문에 위의 코드처럼 반복문의 조건을 설정했다.
첫 번째 반복문의 i = 0
i = 0은 버거를 만들고 바뀐 리스트를 다시 탐색하도록 만든다.
else: i += 1
현재 위치에서 햄버거를 만들 수 없는 경우, 다음 재료로 이동하기 위한 것
실행 결과
아까는 반복이 안되서 문제가 있었던 것이니 while문을 통하면 반복이 리스트의 끝까지 실행됨으로 무조건 성공한다.
라고할뻔...
pop 연산이 많아서 그런가... 싶어서 del이라는 파이썬의 예약어가 존재한다.
del은 pop처럼 리스트의 요소를 삭제하는 예약어로 pop과 비슷한 역할을 한다.
pop부분을 del로 바꿔보자
del ingredient[i:i+4]
연산 처리과정이 조금 더 간단해졌으니 실행결과가 기대되는 부분.
시간이 줄어들긴 했다....
해결법(?)
일단 다른 분의 코드를 찾아봤다.
https://velog.io/@nellroll/%ED%96%84%EB%B2%84%EA%B1%B0-%EB%A7%8C%EB%93%A4%EA%B8%B0
def solution(ingredient): answer = 0 i = 0 while i <= len(ingredient)-2: if ingredient[i:i+4] == [1,2,3,1]: del (ingredient[i:i+4]) i = i-3 answer += 1 i += 1 return answer
최대한 비슷한 걸 찾았는데 이분의 코드는 런타임 에러 없이 작동한다.
이 코드와 다른점은 while의 범위와, i를 처리하는 방식이 다른점이다.
사실 while문은 -2나 -3이나 상관은 없는데 포장에 최소한 4개가 필요하므로 상관은 없다.(이것 보다 더 대용량일 경우 차이가 있을지도..)
다만 i를 처리하는 과정은 자세히 봐야 하는데
- 나는 i = 0
- 코드 주인분: i = i - 3
나는 리스트 내용의 변경에 따라 0부터 다시 탐색하는 과정을 거치도록 로직을 구현했다면,
코드 주인분은 i-3을 통해 리스트 삭제 후 삭제하기 전의 값으로 바로 이어갈 수 있도록 구현하셨다.
[2, 1, 1, 2, 3, 1, 2, 3, 1] 에서 첫번째 [1, 2, 3, 4]를 지운다면
[2, 1, 2, 3, 1] 이렇게 되는데
나는 2부터 탐색하도록 한 것이고, i-3은 1부터 하는것이다.
당연히 처음 부터 해야 변경점이 반영된 리스트를 탐색할 수 있다고 생각했는데, 계속 그 전값부터 시작하면 이게 확실히 더 빠르겠다.
끝!
후기. 너무 어려운데..?
