Python | 백준 9012 / 크레인 인형뽑기 게임

https://www.acmicpc.net/problem/9012

9012번: 괄호

• 접근 방식? 
  • 스택에 ( 모양이라면 넣고, ) 모양이라면 스택의 맨 위와 비교하여 ( 모양과 맞다면 넣지 않고 다음으로 넘어간다.
  • VPS인지 아닌지는 스택이 비어있는지 확인하여 판단한다.

> code

N = int(input())
for _ in range(N):
    stack = []
    ps = input()
    for w in ps:
        if not stack:
            stack.append(w)
        else:
            if stack[-1] == '(' and w == ')':
                stack.pop()
            else:
                stack.append(w)
    ans = 'NO' if stack else 'YES'
    print(ans)

 

---

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

프로그래머스

• 접근 방식?
  • 위의 괄호 문제와 유사하게, 인형을 뽑고 스택에 넣는다. 일치한다면 count를 증가시키면 되고, 그렇지 않다면 스택에 넣는다.
  • 하지만 문제는 moves를 보고 board에서 어떻게 인형을 뽑아서 넣을 것인가? 를 생각해야된다.
    • board에는 좌상단부터 인형의 상태가 주어지기 때문에 그냥 뽑을 수는 없을 것이다.
    • 행렬을 바꿔 0이 아닐 경우(빈칸이 아닌 경우)만 각 줄의 스택에 넣어두고, moves에 맞게 각 줄의 스택에서 pop해오면 될 것이라고 생각했다.

 

> code

from collections import defaultdict
def solution(board, moves):
    answer = 0
    stack = []
    board_dict = defaultdict(list) # column_number : [ stack ]
    for i in range(len(board)):
        for data in board[::-1]: # 행렬의 순서 변경, pop()을 하기 위해 거꾸로 집어넣음
            if data[i] != 0:
                board_dict[i].append(data[i])
    for move in moves:
        if board_dict[move-1]:
            p = board_dict[move-1].pop()
            if not stack or stack[-1] != p:
                stack.append(p)
            else:
                stack.pop()
                answer += 2
    return answer

좀 더 좋은 방식이 있는지 프로그래머스의 다른 사람의 풀이를 보다가 대부분의 풀이가

for i in moves:
    for j in range(len(board)):
    	if board[j][i-1] != 0:
        	stack에 넣고 보드에서 0으로 변경.
        이후 비교

하는 식으로 그대로 위에서부터 검사하는 식으로 되어 있었다. ( 사실 이게 좀 더 명확하고 좋아 보인다. )

또한 board 데이터를 pop하거나, 없애지 않고 해당 자리의 인형 번호를 0번으로 바꿔준다. ( 이 방식도 좋아 보인다. )

위의 부분들은 다른 사람들의 코드를 보면서 나의 접근 방식보다 나은 부분이라고 생각하고, 아래는 나의 접근방식에서 코

드적으로 개선할 부분이 있었는지 확인하는 부분이다.

cols = list(map(lambda x: list(filter(lambda y: y > 0, x)), zip(*board)))

행렬의 순서를 열, 행 구조로 변경하는 부분에서 괜찮은 방식이 있었다.

위의 코드를 해석해보자면, board의 모든 행을 zip(*board) 를 통해 unpacking한 후 zip해준다. 이후 앞의 람다 함수에서, 인형이 있는 셀들만 필터링하여 다시 list로 묶어준다. 람다 함수를 두번 쓴 이유는 2차원 행렬이었기 때문에

첫 번째 lambda x:에는 zip(*board)가 들어가고, lambda y: 에서 각 줄의 리스트가 들어가기 때문에 인형이 있는 셀들만(0보다 큰) 가져올 수 있는 것이다. 이후 다시 리스트로 묶어내 반환해준다.  이렇게 되면 결국 각 열마다의 인형들이 들어오게 된다. 이 코드에서 cols 결과는 인형이 바닥에 있을 수록 리스트의 뒤에 위치하기 때문에 moves를 통해 인형을 꺼내올 때에는 pop(0)을 이용하게 된다. ( queue 형태 )