on1ystar 머릿속을 정리, 기록하는 곳

<프로그래머스 level 1-python> 크레인 인형뽑기 게임

21 Jan 2021

https://programmers.co.kr/learn/courses/30/lessons/64061?language=python3#

문제 요약

문제 설명을 간단히 하자면 입력으로 2차원 리스트 board와 1차원 리스트 moves가 주어진다.

  • board : 인형이 들어있는 격자
  • moves : 뽑기 크레인의 위치

board를 행렬로 나타낸 모습이 인형이 들어있는 격자 모양이며 인형이 없으면 0, 있으면 1~100이 들어있다. 여기서 1~100의 각 숫자는 각각 다른 인형의 모양이다.

moves의 숫자는 그림에서 보이는 것처럼 왼쪽부터 카운트한 크레인의 위치인데, 주의해야 할 점은 0부터 시작이 아니라 1부터 시작이다.

크레인이 격자 무늬를 차례로 내려가다가 인형을 발견하면 인형을 뽑아 오른쪽 바구니에 담는 인형뽑기 게임이다. 당연히 인형이 뽑힌 위치의 값은 0이 되며, 바구니에 담기면 그 위치에 인형의 숫자가 들어가게 된다.

단, 오른쪽 바구니에 같은 인형이 연속으로 2개가 쌓이면 사라진다.

결과적으로 사라진 인형의 개수를 return 해야 한다.

(자세한 설명은 위 문제 링크를 참고)

제한 사항

  • board 배열은 2차원 배열로 크기는  5 x 5 이상  30 x 30 이하입니다.
  • board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
    • 0은 빈 칸을 나타냅니다.
    • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
  • moves 배열의 크기는 1 이상 1,000 이하입니다.
  • moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

문제 풀이

이 문제를 처음에 보고 먼저 생각한 것은 2차원 리스트를 moves를 이용해 잘 순회해야겠다는 생각이었는데, moves의 숫자는 board의 column 인덱스+1을 나타낸다. 따라서 moves를 기준으로 순회를 한다면 이중 for문이 사용 되는데, outer for문은 moves로 column을, inner for문은 board의 위쪽에서 부터 접근할 수 있도록 row를 차례로 순회하도록 했다.

def solution(board, moves):
    answer = 0
    basket = []
    for move in moves:
        for i in range(len(board)):
            if board[i][move-1] != 0:
                basket.append(board[i][move-1])
                board[i][move-1] = 0
                break

이때 만약 if board[i][move-1] != 0: 인형이 있다면 basket 리스트에 그 값을 append 하고, 0으로 초기화 시켜준 뒤, 크레인의 다음 moves로 넘어간다.

여기까지가 인형을 바구니에 담는 과정이다. 이제 바구니에서 같은 인형이 연속으로 담겨 있다면 이를 카운팅 하는 로직을 넣으면 되는데, 한 가지 고민한 부분이 바구니에 담는 과정에서 만약 같은 인형이 연속으로 담긴다면, 혹은 담길 예정이라면 바구니에 담지 말고 인형을 사라지게 하는 식으로 추가를 할 지 고민했다. 간단히 말해서

  1. 바구니에 넣으면서 카운팅
  2. 바구니에 다 넣고 나중에 따로 카운팅

1번째 방법은 기존에 알고 있던 방식으로 처리를 하면 됐다. 그래서 처음에는 1번 방법으로 코드를 짠 뒤 제출했다.

def solution(board, moves):
    answer = 0
    basket = [0]
    for move in moves:
        for i in range(len(board)):
            if board[i][move-1] != 0:
                if board[i][move-1] == basket[-1]:  # 바구니에 담기 전 검사
                    answer += 2
                    board[i][move-1] = 0
                    basket.pop()
                    break
                else:
                    basket.append(board[i][move-1])
                    board[i][move-1] = 0
                    break
    return answer

참고로 basket = [0]으로 초기화 시켜준 이유는, 빈 리스트에서 basket[-1] 으로 접근하면 index 에러가 발생하기 때문에다.

2번째 방법은 스택이나 큐를 상용하면 좋을 것 같았다. 처음에는 바구니를 for문으로 순회하면서 검사할까 하다가, 중간에 원소를 삭제하는 연산을 .pop(i) 로 하면 시간복잡도가 O(n)이므로 스택이나 큐를 사용하는 효율을 내지 못한다. 그렇다고 큐나 스택 하나만 사용하면 당장 1칸 위에 같은 인형은 간단하게 지울 수 있지만, 그 인형들이 사라지면서 아래 있던 인형과 위 2칸의 인형이 같아지는 경우 다시 검사하는 로직이 추가되야 한다.

그래서 가장 좋은 방법은 예전에 사용했었던 스택 2개를 이어 붙이는 식이라고 생각했다.

while True:
    if len(basket) == 0:
        break
    if basket[len(basket)-1] == temp[-1]:
        basket.pop()
        temp.pop()
        answer += 2
    else:
        temp.append(basket.pop())
return answer

if len(basket) == 0:으로 basket이 다 비워질 때까지 순회하면서 temp에 인형을 하나 씩 옮겨 담는다. 단, 만약 basket의 마지막 인형과 temp의 마지막 인형이 같으면 동시에 pop시켜준 뒤 answer += 2 로 카운팅 시킨다.

추가로 확인하면 좋은 자료

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O)

전체 코드 첨부

on1ystar/algorithm-problem-solving-codes

Related posts