[Python] Lv1.크레인 인형뽑기 게임

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

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

 

 

 

문제 설명

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

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

 

나의 접근방법 및 풀이

처음에 문제를 읽고 그림을 봐도 한 번에 이해가 되지 않았다. 그래서 직접 그려보고 문제의 순서를 하나하나 따라갔더니 어떤 방식으로 풀어야하는지 감이 왔다.

처음에는 moves를 어떻게 활용할까 싶었는데, 천천히 생각해보니까 2차원 배열 board의 'column', 즉 열의 의미였다.

moves = [1, 5, 3, 5, 1, 2, 1, 4]를 해석하자면, '1'은 2차원 배열에서 첫번째 column을, '5'는 2차원 배열에서 다섯번째 column을 의미한다는 것이다. 

그렇다면 이제 문제에 어떻게 적용하는 것이 관건이다.

result = []     ## 뽑은 인형 쌓는 곳
    count = 0
    for m in moves:
        m = m-1
        for i in range(len(board)):     ## 인형 뽑기 파트
            if board[i][m] != 0:
                result.append(board[i][m])
                board[i][m] = 0     ## 인형 뽑아서 비어있으니 0으로 채워주기
                break       ## 인형은 해당 위치에서 하나만 뽑을 거다.

:우리의 목표는 moves의 위치 중 가장 상위에 있는 인형을 뽑아, result에 넣는 것이다. 

<뽑기 전>

그렇다면 moves의 요소를 차례대로 가져와 → for()문을 이용하여

뽑기 전에,  배열의 인덱스는 0부터 시작하기 때문에 1~5로 구성된 moves의 요소들의 값을 -1씩 해야한다.  → m = m-1

 

<본격적으로 인형 뽑기>

인형의 위치를 알려주었으니(m) 몇 번째 행에 위치했는지 알아야한다. → for()문 이용해서 board의 길이만큼 반복

우리는 해당 위치에서 맨 위에 있는 것부터 뽑아야 한다. 즉, 0이 아닌 수가 맨 처음 나올때이다. → if board[i][m] != 0:

해당 위치에 있는 인형의 종류(값)를 result에 추가한다. → result.append(board[i][m])

인형을 뽑은 자리는 인형이 없으므로, 해당 위치의 값을 0으로 해줘야 한다. → board[i][m] = 0

우리는 해당 위치에서 가장 꼭대기부터 아래로 인형을 가져오기때문에, 맨 처음 0이 아닌 수, 즉 인형을 발견하면 해당 위치에서 뽑기는 종료해야 한다. → break문

 

## 에러 발생
##            if len(result) != 0:
##                for j in range(len(result)):
##                    if result[i] == result[i+1]:
##                        del result[i]
##                        del result[i+1]
##                        count += 2
##                        break
##    return count

if len(result) > 1:        
            if len(result) > 2:
                if result[-2]==result[-1]:  ## 리스트 마지막 2개 원소가 같다면
                    result=result[:-2]      ## 슬라이싱해서 result는 그 전까지
                    count += 2              ## 한 번 터트릴때 2개 씩 터짐
            else:
                if result[0] == result[1]:
                    result = []
                    count += 2
    return count

result에 인형을 추가하고, 이전에 들어왔던 인형의 종류와 방금 들어온 인형의 종류가 같은 지 확인을 해야한다.

처음에 생각했던 것은 이중 for()문을 이용해서 i, i+1 위치의 요소를 비교하는 것이었지만 범위를 벗어나면 에러가 발생하여 해결하지 못했다.

그런데 다시 생각을 해보니 인형은 한 번 터트릴 때 2개씩만 터트릴 수 있다. 즉, result에서 마지막 2개 인형만 비교해서 같은 경우 터트리면 된다.

그런데 이때 생각해야할 조건이 있다.

바로 result의 길이가 1이하, 2일때, 3이상일때이다.

바로 마지막 두개의 요소만 비교하면 길이가 1이하, 2일때는 리스트의 범위에서 벗어나 에러가 나기 때문이다.

그래서 두 개의 원소만 비교할 것이므로, 우선 result의 길이는 1이상이어야 한다.

● result의 길이가 3이상일 경우

마지막 2개의 원소를 비교하고, 둘이 같다면 인형을 빼야하기 때문에 슬라이싱을 이용하여 result를 재정비한다.

● result의 길이가 2일 경우

첫번째, 두번째 원소만 비교하며, 같은 경우 result를 빈 리스트로 다시 설정한다.

그리고 두 경우 모두, 인형을 터트린다면 한 번에 2개씩 터트리기 때문에 count에 +2를 해준다.

 

<전체 코드>

def solution(board, moves):
    result = []     ## 뽑은 인형 쌓는 곳
    count = 0
    for m in moves:
        m = m-1
        for i in range(len(board)):     ## 인형 뽑기 파트
            if board[i][m] != 0:
                result.append(board[i][m])
                board[i][m] = 0     ## 인형 뽑아서 비어있으니 0으로 채워주기
                break       ## 인형은 해당 위치에서 하나만 뽑을 거다.
        if len(result) > 1:        
            if len(result) > 2:
                if result[-2]==result[-1]:  ## 리스트 마지막 2개 원소가 같다면
                    result=result[:-2]      ## 슬라이싱해서 result는 그 전까지
                    count += 2              ## 한 번 터트릴때 2개 씩 터짐
            else:
                if result[0] == result[1]:
                    result = []
                    count += 2
    return count

 

다른 풀이

def solution(board, moves):
    stacklist = []
    answer = 0

    for i in moves:
        for j in range(len(board)):
            if board[j][i-1] != 0:
                stacklist.append(board[j][i-1])
                board[j][i-1] = 0

                if len(stacklist) > 1:
                    if stacklist[-1] == stacklist[-2]:
                        stacklist.pop(-1)
                        stacklist.pop(-1)
                        answer += 2     
                break

    return answer

위의 코드에서는 '인형 뽑기' → '연속되는 인형 비교' → break 순서로 진행했다.

'인형 뽑기' 파트는 비슷하지만, '연속되는 인형 비교' 파트에서 pop을 이용해서 진행했다.

 뽑은 인형이 있는 stacklist에서 마지막에서 두 개의 인형을 뽑아 같다면 pop()을 이용했다. 

 

 

 

 

사실 이 문제는 문제 클릭했다가 그림보고 '나는 아직 안 되겠구나'하고 뒤로가기를 몇 번 눌렀던 문제이다. 다른 카카오 문제를 풀다 잘 안풀려서 다른 문제 풀어야지 하면서 문제를 탐색하다가 못 풀어도 일단 도전해보자 하는 마음으로 풀어봤다. 시간이 조금 오래 걸리긴 했지만 다른 사람의 코드를 보지 않고 스스로 풀어서 뿌듯했다.