문제

https://programmers.co.kr/learn/courses/30/lessons/64061

나의 코드

"""
1. 아이디어
크레인을 작동시킬 순서가 담긴 moves를 탐색하면서 인형이 존재하는 경우 바구니에 집어넣는다.

2. 시간복잡도
첫번째 반복문에 대하여 이중 반복문으로 돌기 때문에 O(n^2)이다. (append연산은 O(1)이라서 무시)
"""

def solution(board, moves):
    answer = 0
    n = len(board)
    basket = []
    
    # board[j][i-1] 에 대한 수식은 직접 그림을 그려보면 이해된다.
    for i in moves: # 순서대로 뽑기를 진행한다.
        for j in range(n):
            if board[j][i-1] > 0: # 0 이상인 경우는 인형이 있다는 것을 의미한다.
                basket.append(board[j][i-1]) # 바구니에 담는다
                board[j][i-1] = 0 # 인형을 뽑았으면 뽑은 자리는 비었다고 표시해준다.
                break
    
    # 이전의 값을 기록하기 위해 변수 리스트를 생성했다. 리스트로 작성한 이유는 인형이 만약 터지게 되면 그 이전의 값들도 참조해야 하기 때문에 리스트로 작성했다. 
    recent_num = [ basket[0] ] 
    for i in range(1, len(basket)):
        if not recent_num: # 만약 참조할 이전의 값이 없다면(인형이 다 터진경우) 현재의 값을 넣고 다음 반복문으로 넘어간다.
            recent_num.append(basket[i])
            continue
            
        if recent_num[-1] == basket[i]: # 만약 인형 2개가 겹치는 경우
            recent_num.pop() # 참조하고 있는 인형의 숫자를 제거한다.
            answer += 2 # 인형을 터뜨린 개수.
        else:
            recent_num.append(basket[i]) # 인형 2개가 겹치치 않는다면 현재의 인형에 해당하는 숫자를 넣는다.
    
    return answer

다른 사람의 코드

def solution(board, moves):
    
    pop_cnt = 0 # 터뜨려진 인형의 개수
    n = len(board)
    stack = [] # 스택
    
    for i in moves:
        for j in range(n):
            if board[j][i-1] != 0: # 인형이 존재한다면
                stack.append(board[j][i-1]) # 스택에 넣고
                board[j][i-1] = 0 # 인형을 뽑았으니 없다고 표시한다.
                
                if len(stack) >= 2:
                    if stack[-1] == stack[-2]: # 마지막에 들어온 인형 2개를 비교한다.
                        stack.pop()
                        stack.pop()
                        pop_cnt += 2
                        
                break
    
    return pop_cnt

느낀점

전형적인 스택의 쉬운문제 인것 같은데 괜히 어렵게 생각해서 복잡하게 푼 것 같다.

인형을 뽑으면서 중간 중간 같은 인형이 연속으로 있는지 확인하는게 이 문제의 핵심인 것 같다.(나처럼 다 뽑아놓고 값을 서로 비교하지 말고)

자료구조를 잘 활용해서 풀어야 겠다.