2019 카카오 겨울 인턴쉽_크레인 인형뽑기 게임

작년에 경험삼아 쳐본 2019 카카오 인턴쉽 알고리즘 코딩테스트 문제를 프로그래머스에서 발견해서 다시 한번 풀어본다.

그 당시 이문제만 풀고 나머지 문제는 시간/코딩 능력 상 못 풀었었는데 다시 푸니까 이상한데에서 헤매서 또 시간이 오래 걸렸다.. 사소한 실수를 반복하지 않도록 연습할 필요가 있을 것 같다. 

---

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/64061?language=python3

 

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

 

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 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 배열의 가로 크기 이하인 자연수입니다.

---

풀이나 지인에게 질문 했을 때 자료구조 스택 관련 문제라고 한다. 관련 내용은 공부한 적이 없으므로.. 헤맨것도 있고 실수도 많이 있었다.실제 다른 사람 풀이를 봤을때 내 풀이랑 큰 차이가 없어서 내가 구현한게 스택? 인가 싶기도 하다.

 

 

1. 내 풀이

def solution(board, moves):
    temp = ['x']
    answer = 0
    
    for move in moves:
        for j in range(0,len(board[0])):
            if board[j][move-1] == 0:
                pass
            elif board[j][move-1] != 0:
                if board[j][move-1] == temp[-1]:
                    temp.pop()
                    answer = answer + 1
                else:
                    temp.append(board[j][move-1])
                board[j][move-1] = 0
                break;
    return answer*2

약간의 꼼수를 썼는데 각 인형들은 숫자형태로 들어가기 때문에 절대 문자인 'x'와 같을 일이 없어 길이 검사할때 편한 측면이 있다. 실제로 이렇게 코딩해도 되는지는 사실 잘 모르겠다.. 질문할 필요가 있음

 

2. 다른 사람 풀이1

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

내 풀이랑 약간의 차이점이 있다면 

1. 나는 새로운 성분과 마지막 성분이 같다면 그냥 리스트의 마지막 성분을 pop하는 형식이었고 이분은 리스트에 append한다음에 검사한 후 pop을 두번 실행하는 스타일을 사용

2. 나는 문자열을 리스트에 추가하는 꼼수?를 썼지만 이분은 정직하게 if문을 이용해서 길이를 검사했다는 점

이 다르다고 할 수 있다.

 

3. 다른 사람 풀이2

 

def solution(board, moves):
    answer = 0
    box = []
    for move in moves:
        found = 0
        for row in board:
            if (row[move - 1]):
                found = row[move - 1]
                row[move - 1] = 0
                break
        if (found):
            box.append (found)

    i = 0
    while (i < len(box) - 1):
        if (box[i] == box[i+1]):
            print (box[i:i+1])
            box.pop (i)
            box.pop (i)
            if (i >= 1):
                i -= 1
            answer += 2
            continue;
        i += 1
    return answer

컴공 지인이 조언 해준 방법과 비슷하다.

일단 Box안에 들어갈 리스트를 작성 후 while문을 활용해 pop해주는 방식이다.

while문 안의 구조를 잘 살펴볼 필요가 있겠다..