처음에 stack과 deque를 이용하여 문제를 한 큐에 통과했다. 하지만, 요새 들어 발견한 문제점은 예외경우를 잘 생각 못 한다는 것이다. 그러다가 발견한 것은 스스로 생각했을 때 논리를 다양한 방법으로 접근하면 내가 생각치 못한 테케들을 발견할 수 있다. 이 말은 즉 모든 테케를 고려하지 않고(스스로는 모든 테케를 고려했다 생각함😭) 코드를 짰는데 다 통과한 경우가 많은 경우가 있어 예외의 경우가 있다는 생각조차 못한 것이다. 이 문제가 딱 그러해서 블로그로 정리해 보려고 한다.
일단은 먼저 통과한 코드부터 보자면 아래와 같다.
🍀 stack & deque를 이용한 풀이
- ingredient를 deque에 담아 deque가 빌 때까지 루프를 돈다.
빵(1)인 경우에 stack의 마지막 3개의 요소와 현재 재료가 더해서 햄버거인지 체크한다.빵(1)이 아닌 경우는 스택에 넣어준다.
로직은 생각보다 단순하다. 사실 여기서 막힌 부분이 있다면 continue를 작성하지 않아 시간이 조금 걸렸다. 이 말은, continue를 쓰지 않으면 햄버거인 경우에 빵 재료를 다시 stack에 넣어주게되는 논리적 오류가 발생한다. 이해가 안 된다면 TC = [1, 2, 3, 1, 2, 3, 1]를 통해 알 수 있다. 햄버거를 만들면 [2, 3, 1]이 되어야 하는데 [1, 2, 3, 1]이 되 햄버거를 하나 더 만드는 경우가 생긴다.
from collections import deque
def solution(ingredient):
answer = 0
stack = []
q = deque(ingredient)
while q:
cur_v = q.popleft()
if cur_v == 1 and (stack[-3:] + [cur_v]) == [1, 2, 3, 1]:
stack[-3:] = []
answer += 1
continue # [1, 2, 3, 1, 2, 3, 1]같은 경우에 index = 3의 값인 1은 안 더해져야 하는데
# 아래 코드 때문에 더해주어서 append가 안 되게 한다.
stack.append(cur_v)
return answer
📒 이 문제를 풀 때 queue가 빌 때 까지 배열의 앞단에서 요소를 계속 빼면서 루프를 돌게된다. 이 때 만약에 배열의 길이가 엄청 길고 일반배열을 사용한다고 가정하면,
pop(0)을 통해 앞의 요소를 빼게되면O(n)시간이 걸려testcase -> 3~9와 12가 시간초과가 나게 된다.
만약에 일반 배열에서 앞의 요소를 빼는 왜 O(n)을 갖게 되는지 모른다면 여기(linked list를 이용한 queue구현)를 참고하자.
🍀 다른 풀이
- 배열을 join을 시켜 햄버거기 일치하는 개수를 세어 answer에 더한다 1️⃣ ❌
- 햄버거라면 햄버거인 부분은
빈 문자열로 만들어준다.
def solution(ingredient):
answer = 0
str_ingredient = ''.join(map(str, ingredient))
# 반례 [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1] -> 3개
while count:=str_ingredient.count('1231'):
answer += count
str_ingredient = str_ingredient.replace('1231', '')
return answer주석에도 보면 알겠지만 [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1] -> [1, 1, 2, 3, 1, 2, 3, 1] -> [1, 2, 3, 1]로 총 3개가 나와야 하는데 위의 코드대로면 [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1] -> [1, 1, 2, 3]로 총 2개가 나오는 상황이 발생한다. 즉, 문제의 조건에서 상수는 순서에 맞게 햄버거를 1개씩 포장한다는 것을 위반한 것이다.
개선
def solution(ingredient):
answer = 0
str_ingredient = ''.join(map(str, ingredient))
while found_idx:=str_ingredient.find('1231') >= 0:
answer += 1
str_ingredient = str_ingredient[:found_idx] + str_ingredient[found_idx + 4:]
return answer하지만, 3~12 테케를 통과하지 못했다...;;
분명 로직이 맞는 거 같고 아무리 생각해도 예외를 못찾겠어서 아래 코드를 통해 예외 테케를 찾고자 했다. 😭😭😭
예외 테케 찾는 코드
from collections import deque
import random
def create_tc(num_tsc, num_ingredients):
tcs = []
for _ in range(num_tsc):
tcs.append([random.randint(1, 3) for _ in range(random.randint(10, num_ingredients))])
return tcs
def solution_with_find(ingredient):
answer = 0
str_ingredient = ''.join(map(str, ingredient))
while found_idx := str_ingredient.find('1231') >= 0:
answer += 1
str_ingredient = str_ingredient[:found_idx] + str_ingredient[found_idx + 4:]
return answer
def solution_with_stack(ingredient):
answer = 0
stack = []
q = deque(ingredient)
while q:
cur_v = q.popleft()
if cur_v == 1 and (stack[-3:] + [cur_v]) == [1, 2, 3, 1]:
stack[-3:] = []
answer += 1
continue
stack.append(cur_v)
return answer
test_cases = create_tc(50, 30)
stack_answer = []
find_answer = []
for tc in test_cases:
if solution_with_find(tc) != solution_with_stack(tc):
print("-"*10, f"tc: {tc}", "-"*10)
print("find_result", solution_with_find(tc))
print("stack_result", solution_with_stack(tc))
stack_answer.append(solution_with_stack(tc))
find_answer.append(solution_with_find(tc))
print(stack_answer == find_answer)이렇게 테스트 케이스에 대해 어떤 값이 나오는지 확인해 본 결과 로직문제가 아닌 논리적 오류였다....ㅋㅋㅋㅋ
문제는 while의 조건문에서 났다.
def solution(ingredient):
answer = 0
str_ingredient = ''.join(map(str, ingredient))
while found_idx:=str_ingredient.find('1231') >= 0: 👈 ❌
answer += 1
str_ingredient = str_ingredient[:found_idx] + str_ingredient[found_idx + 4:]
return answer조건 -> found_idx:=str_ingredient.find('1231') >= 0라면
found_idx = 찾은 index값이 아닌boolean임을 확인했다. 오류는 연산순서에 있었으며 이는 아래와 같이 괄호로 연산순서를 조정하여 해결했다.
while (found_idx:=str_ingredient.find('1231')) >= 0 코드를 수정한 결과
테케 5와 12에서 뻑이났다.
이는 find -> O(n)이고 slicing -> O(n)이기 때문에 시간초과가 난 것 같아 O(n)으로 시간 복잡도를 줄이면 해결될 것 같았다.
코드를 아래와 같이 엎었다.
def solution(ingredient):
answer = 0
stack = []
for value in ingredient:
stack.append(value)
if stack[-4:] == [1, 2, 3, 1]:
answer += 1
stack[-4:] = []
return answer🍀 마치며
예외 케이스를 고려하기 위해 거의 4시간이란 시간을 쏟아부었지만 예외 케이스가 아닌 연산순서에서 잠재적 오류가 발생하였다... ㅜㅜ
하지만, 여러가지 풀이를 통해서 다양한 사고력을 갖추었으면 하는 스스로의 바램이다.
그리고 어떤 일이 있었는지 기록으로 남겨두어 다시 참고할 때 본인이 어디서 막혔고 뭐가 문제인지 확인하니 좋다.
같은 문제를 풀더라도 문제점을 고치지 않으면 항상 같은 곳에서 실수하고 문제를 만들기 때문에 이러한 악습을 고칠 수 있으면 한다.
