[코딩테스트] 연습문제 - 햄버거 만들기

 

---

문제

 

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

프로그래머스

 

 

차례로 쌓이는 재료의 순서가 1, 2, 3, 1일 경우 햄버거를 만들고 카운트 하는 문제

 

햄버거를 만들고 나서 남아있는 재료들과 새로 쌓이는 재료가 다시 햄버거가 될 수도 있다.

 

 

---

전략

 

01. 스택, 클래스

 

 스택에 재료들이 올바른 순서대로 배열되어 있을 때 스택의 내부에서 알아서 판단하게끔 하고 싶었다. Burger클래스를 만들고 원래 재료의 순서와 다른 재료가 들어오면 새로운 Burger인스턴스를 스택에 넣어주고, 순서가 같은 재료가 들어오면 기존 Burger인스턴스에 그 재료를 추가하면 차례대로 계산할 수 있다. 이때 Burger인스턴스 안에서 재료의 순서인 [1, 2, 3, 1]이 채워진다면 True를 리턴하고 그 때 그 인스턴스를 제거하면서 카운트를 해주면 된다.

 

 

---

풀이

class Burger:
    def __init__(self):
        self.stack = [1]
        self.order = (1, 2, 3, 1)
    
    def add(self, ingredient):
        self.stack.append(ingredient)
        if self.stack == [1, 2, 3, 1]:
            return True
    
    def __del__(self):
        return
    
    def next_one(self):
        return self.order[self.order.index(self.stack[-1]) + 1]
    
    def __repr__(self):
        return f"{self.stack}"

def solution(ingredient):
    stack = []
    count = 0
    
    for i in ingredient:        
        if stack:
            if stack[-1].next_one() == i:
                if stack[-1].add(i):
                    count += 1
                    del stack[-1]
            elif stack[-1].next_one() != i:
                if i > 1:
                    stack.clear()
                else:
                    stack.append(Burger())
        else:
            if i == 1:
                stack.append(Burger())
    
    return count

 

stack = []
count = 0

 

 먼저 각 버거 인스턴스들이 들어갈 stack 배열과 완성된 버거의 개수를 셀 count를 만들어준다.

 

for i in ingredient:        
        if stack:
            # ...(생략)...
        else:
            if i == 1:
                stack.append(Burger())

 

 다음으로 ingredient안의 재료(i)를 차례로 순회하는데, 이때 stack에 아무것도 없다면(else) i == 1인지를 검사해서 새로운 Burger 인스턴스를 만들어 준다. 이유는 순회하는 처음 값들 중에서 1이 아닌 다른 값들을 버리기 위해서다. 입출력 예 1번이 그렇다.

 

class Burger:
    def __init__(self):
        self.stack = [1]
        self.order = (1, 2, 3, 1)
    
    def add(self, ingredient):
        self.stack.append(ingredient)
        if self.stack == [1, 2, 3, 1]:
            return True
    
    def __del__(self):
        return
    
    def next_one(self):
        return self.order[self.order.index(self.stack[-1]) + 1]
    
    def __repr__(self):
        return f"{self.stack}"

 

 이제 Burger클래스를 보면 __init__메소드에서 self.stack = [1]이 기본적으로 세팅된다. 새로운 Burger인스턴스는 재료가 1일 때 생성되기 때문이다. add메소드에서는 하나의 재료인 ingredient를 파라미터로 받고 self.stack에 넣어준다. 그리고 이 stack이 1, 2, 3, 1순서라면 True를 리턴해준다. 그리고 각 Burger인스턴스가 다음에 받아야 할 값이 뭔지 간단히 하기 위해 next_one 메소드로 다음에 받아야 할 값을 리턴하도록 했다

 

 그리고 나머지 __del__, __repr__ 매직 메소드는 각각 인스턴스를 삭제하기 위해, 그리고 메인 solution함수 안에서 stack을 출력할 때 메모리 주소가 아닌 인스턴스의 stack값들을 출력하기 위해서 만들어 주었다.

 

if stack[-1].next_one() == i:
    if stack[-1].add(i):
        count += 1
        del stack[-1]
elif stack[-1].next_one() != i:
    if i > 1:
        stack.clear()
    else:
        stack.append(Burger())

 

 이제 다시 원래 함수로 돌아와서, 초기 i == 1인 재료에서 Burger인스턴스가 처음 하나 생성되고 난 뒤에는 if stack이 True이므로 위의 코드가 실행된다. stack[-1] 즉, stack의 가장 최근에 삽입된 Burger인스턴스에서 다음에 필요한 값이 i와 같다면, i 재료를 add하고 True라면(= 인스턴스의 add메소드에서 True을 리턴한다면) count를 1 더하고, 해당 Burger인스턴스를 삭제한다.

 

 가장 최근에 삽입된 Burger인스턴스에서 다음에 필요한 값이 i와 다르다면 두 가지 경우를  생각해볼 수 있다. 만약 Burger 인스턴스의 self.stack이 [1]인데 들어가려는 재료 i = 3이라면 앞선 모든 재료들로는 버거를 만들 수 없다. [3]일 때 i = 2인 경우도 마찬가지다. 따라서 이러한 경우인 i > 1로 stack을 아예 비워준다. 반대로 i = 1인 경우 이 재료로부터 새로운 버거를 만들 수 있는 가능성이 있으므로 새로운 Burger 인스턴스를 생성해 추가해준다.

 

 

정확도 테스트

 

 

---

다른 사람의 풀이

 

1. 스택

 

def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            for i in range(4):
                s.pop()
    return cnt

 

 간단한 스택으로 풀었다..스택으로 s 배열에 하나씩 추가할 때마다 마지막 4개의 재료를 검사해서 [1, 2, 3, 1]인 경우 그 재료를 pop()하고 cnt를 +1 해준다. 위 코드도 O(n) 시간 복잡도이며 속도도 이게 2-3배 더 빠르다..

정확성 테스트