[python] 프로그래머스 64061번 : 크레인 인형뽑기 게임 (slicing)

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

코딩테스트 연습 - 크레인 인형뽑기 게임

 

 

1. 구현

위처럼 각 배열에서 인형들의 열 정보는 moves에 저장되어 있지만

인형이 들어있는 행 정보에 대한 배열이 없어 rows 라는 배열로 관리해주었다.

예를 들어, moves 배열에 3이라는 값이 들어있다면

3번째 위치인 idx 기준으로 2인 열을 탐색할텐데, 0이 들어있지 않은 행을 0부터 n-1까지  (board의 크기 n) 찾아봐야 한다.

한 번 등장하면 그냥 for문으로 0이 아닌 인형 값을 찾아주면 되지만 moves에서 3이 여러번 등장한다면 계속해서 for 문을 돌아야하기에 비효율적이다.

따라서 따로 인형이 들어있을 행 위치를 rows 배열로 관리해주었다. 

 

rows[ i ] = i번째 위치에서 인형을 뽑을 때 인형이 위치할 행 인덱스 값 저장  

 

인형을 찾으면 이제 다음 인형이 있을 위치인 rows[m] + 1 으로 값을 넘겨주었는데 행은 n-1까지만 접근할 수 있어

if rows[m] < n-1:
    rows[m] += 1 와 같이 관리해주었다.

그리고 

주어진 예제를 보면 알 수 있듯이 1번째 위치에는 인형이 두 개 뿐인데 1번 위치에 3번 접근하기 때문에 마지막에는 인형을 뽑지 못한다. 이걸 구현해주기 위해 우선 인형을 뽑으면 뽑은 인형은 board 배열에서 0으로 초기화하여 관리해주었다.

그리고 stack에 원소를 저장할 때 0인 값이라면 저장하지 않고 무시하도록 하였다.  

def solution(board, moves):
    answer = 0
    n = len(board)
    # 각 열마다 인형이 들어있는 행 index 정보 저장 
    rows = [0]*n
    stack = []
    count = 0
    # 크레인의 위치 정보에 대해 
    for move in moves:
        m = move - 1
        for i in range(n):
            # 인형이 들어있는 위치라면 
            if board[rows[m]][m] != 0:
                # 같은 모양의 인형이 쌓인 경우 
                if stack and stack[-1] == board[rows[m]][m]:
                    count += 2
                    stack.pop()
                else:
                    # 이미 stack에 쌓인 인형이 아니라면  
                    if board[rows[m]][m] != 0:
                        stack.append(board[rows[m]][m])
                # stack에 쌓인 인형은 0 처리 
                board[rows[m]][m] = 0
                # 다음 행 번호로 인덱스 증가
                if rows[m] < n-1:
                    rows[m] += 1
                break
            # 인형이 들어있는 위치가 아니라면 위치 증가
            else:
                rows[m] = i+1

    return count

2. 다른 풀이

아래 코드는 행 정보를 따로 배열로 저장하지 않고 바로 for문을 돌린 방식이다.

만약 n의 크기가 엄청 크게 주어졌다면 매우 비효율적이지만 관리하는 변수가 더 적어서 직관적으로 이해하기엔 쉽다. 

이러한 풀이법을 보고 아직 slicing에 대해 미숙하다는 점을 알게 되었다!

def solution(board, moves):
    answer = 0
    n = len(board)
    stack = []
    for move in moves:
        for i in range(n):
            # 인형이 들어있다면 
            if board[i][move-1] > 0:
                stack.append(board[i][move-1])
                board[i][move-1] = 0
                # 방금 저장한 인형과 이전에 저장한 인형이 같다면
                if stack[-1:] == stack[-2:-1]:
                    answer += 2 
                    # 두 인형 정보 제거 
                    stack = stack[:-2]
                break
    return answer

 

[리스트 slicing 정리]

stack = [1,2,3,4,5]
print('배열 > ', stack)
print('stack[-2:-1]', stack[-2:-1]) # 마지막-1 번째 원소
print('stack[-1:]', stack[-1:]) # 마지막 번째 원소 
print('stack[-1:-1]', stack[-1:-1]) # []
print('stack[:-1]', stack[:-1]) # 마지막에 위치한 원소를 제외한 배열
print('stack[:-2]', stack[:-2]) # 마지막-1, 마지막에 위치한 원소를 제외한 배열