안녕하세요! 개발자 여러분들.
이번에는 카카오 코딩테스트 풀이 자료를 공유해드리고자 합니다.
누군가에게 도움이 되셨으면 좋겠습니다.

Notion 문서를 velog 에 옮긴 것이라서 보기 불편할 수 있습니다.
더 쉽게 보고 싶으시다면 Notion 문서에서 보셔도 괜찮습니다

📹 0. 해설 영상

📝 1. 오늘의 문제

(질문 링크)

질문 읽기

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

  board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
  moves = [1,5,3,5,1,2,1,4]
  # 4 가 출력되어야 합니다.

고민해보기: 실전 문제처럼 20분 이상을 고민해 본 다음, 아래 방법들을 펼쳐 봅시다!

• 아래 코드를 복사 붙여넣기 하고 함수를 작성해보세요!

  • [코드스니펫] 크레인 인형뽑기 게임

    def solution(board, moves):
        answer = 0
        return answer

✍️ 2. 풀이 방법

2-1. 목표 설정 및 풀이 방법 결정

이 문제에서는 "바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다." 라고 합니다.
즉, 인형을 뽑아 바구니에 저장해두는데, 이 때 같은 게 2개 쌓은 인형 두 개가 없어지게 됩니다.

따라서, 뽑은 순서대로 저장해 놓는 자료구조가 필요합니다.
순서대로 데이터를 저장하는 자료구조는 "스택" 또는 "큐" 입니다!

현재 바구니는 아래서부터 쌓이고 위에서 빠지는 형태이므로 스택을 써야 한다는 것을 유추할 수 있습니다.

우선 우리가 반환해 줘야 하는 것은 "크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수" 입니다.
따라서 answer = 0 을 지정해서 반환해 줍시다.

2-2. 코드 구현 시작

그리고 우리는 스택을 이용해서 바구니를 구현할 것이라고 했습니다.
따라서 그 값을 저장해두기 위한 bucket = [] 라는 변수를 만들어 두겠습니다.

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

그러면 이제 moves 에 따라서 board 의 특정 칼럼의 가장 윗값을 조회해서 bucket 안에 넣어줘야 합니다.
이 말인 즉슨, moves 가 1일 때 board 의 1열을 (실제로는 인덱스 0) 위에서부터 조회해서 빈 값이 아닐 때 bucket 에다 쌓습니다.
그리고 또 moves 가 5라고 한다면 board 의 5열을 (실제로는 인덱스 4) 위에서부터 조회해서 빈 값이 아닐 때 bucket 에다 쌓습니다.

# 아래와 같은 board 에 [1,5,3,5,1,2,1,4] 라는 moves 가 입력된다고 해보겠습니다.
# 0. moves 에서 원소를 하나씩 꺼내면서 board 의 열에 해당하는 가장 위의 원소를 bucket 에 넣으면 됩니다.
[
    [0, 0, 0, 0, 0],
    [0, 0, **1**, 0, **3**],
    [0, **2**, 5, 0, 1],
    [**4**, 2, 4, **4**, 2],
    [3, 5, 1, 3, 1]
] # board

# 1. 첫 번째 원소인 1, 즉 0번째 인덱스의 칼럼인 [0,0,0,4,3] 에서 가장 위의 원소인 4를 꺼내 bucket 에 넣습니다.
[
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 3],
    [0, 2, 5, 0, 1],
    [**4**, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
] # board

-> 

[
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 3],
    [0, 2, 5, 0, 1],
    [**0**, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
] # board

[4] # bucket

# 2. 다음 원소인 5, 즉 4번째 인덱스의 칼럼인 [0,3,1,2,1] 에서 가장 위의 원소인 3을 꺼내 bucket 에 넣습니다.
[
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, **3**],
    [0, 2, 5, 0, 1],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
] # board

->

[
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, **0**],
    [0, 2, 5, 0, 1],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
]# board

[3, 4] # bucket

# 3. 다음 원소인 3, 즉 2번째 인덱스의 칼럼인 [0,1,5,4,1] 에서 가장 위의 원소인 1을 꺼내 bucket 에 넣습니다.
[
    [0, 0, 0, 0, 0],
    [0, 0, **1**, 0, 0],
    [0, 2, 5, 0, 1],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
]# board

->

[
    [0, 0, 0, 0, 0],
    [0, 0, **0**, 0, 0],
    [0, 2, 5, 0, 1],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
]# board

[1, 3, 4] # bucket

# 4. 다음 원소인 5, 즉 4번째 인덱스의 칼럼인 [0,0,1,2,1] 에서 가장 위의 원소인 1을 꺼내 bucket 에 넣습니다.
# 이 때, bucket의 맨 위에 1이 있습니다. 그러면 동일한 1, 1은 제거되고 result 에 2가 추가됩니다!
[
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 2, 5, 0, **1**],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
]# board

->

[
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 2, 5, 0, **0**],
    [0, 2, 4, 4, 2],
    [3, 5, 1, 3, 1]
]# board

[3, 4] # bucket

2-3. 본격적인 코드 구현 시작

이제 위의 내용을 코드로 구현해보도록 하겠습니다!

우선, moves 를 반복문을 통해서 조회합니다.
여기서 move 를 인덱스로 변환해주기 위해서 index 라는 변수에 move - 1 값을 저장합니다.

그러면 어떤 인덱스를 구해야 하는지는 알겠으니, 이 정보를 바탕으로 board 를 조회해야 합니다.
따라서 board 의 row 값들을 row_info 에 담은 뒤, 각 행에서 해당 index 에 있는 열의 원소 값이 0인지 아닌지 확인합니다.

만약 0이 아니라면 bucket 에 append 해서 넣어주고 중단시키면 됩니다!

def solution(board, moves):
    bucket = []
    answer = 0
    
    **for move in moves:
        index = move - 1
        for row_info in board:
            if row_info[index] != 0:
                bucket.append(row_info[index])
                break**
            
    return answer

그런데 이렇게 계속 bucket 에 넣기만 하면 안됩니다!
우리가 해당 row_info[index] 값을 bucket 에 담았다는 것은, 해당 원소의 값을 뽑았다는 것을 의미하므로 0으로 초기화 시켜주는 작업을 해야 합니다.
그래야 맨 위의 인형이 뽑혀져 나갔다는 것을 드러내줄 수 있을 것입니다.

def solution(board, moves):
    bucket = []
    answer = 0
    
    for move in moves:
        index = move - 1
        for row_info in board:
            if row_info[index] != 0:
                bucket.append(row_info[index])
                **row_info[index] = 0**
                break
                
    return answer

또한, 추가적인 로직이 하나 더 필요합니다.
맨 위의 인형과 방금 넣은 인형이 같다면, 그 두 인형을 제거하고 answer 에 2를 추가하는 로직이 필요합니다.

따라서 bucket 의 맨 뒤에 원소가 맨 뒤에서 두번째 원소와 같다면, bucket 의 두 원소를 제거하며 answer 를 2를 더해주는 로직을 추가하면 됩니다.

def solution(board, moves):
    bucket = []
    answer = 0
    
    for move in moves:
        index = move - 1
        for row_info in board:
            if row_info[index] != 0:
                bucket.append(row_info[index])
                row_info[index] = 0
                **if len(bucket) >= 2 and bucket[-1] == bucket[-2]:
                    answer += 2
                    bucket = bucket[0:-2]**
                break
    return answer

2-4. 교훈 및 정리

우리는 이렇게 Stack 을 이용하는 문제를 풀어봤습니다!

실제 코드를 작성하기 전에, 요구사항에 대해서 먼저 분석하고 어떻게 해결할 것인지에 대해서 입력 예시를 통해 생각해보시는 것이 좋습니다.

실제 런타임 시에 변수들이 어떻게 변화되는지에 대해 생각하다보면 "아 이렇게 하면 더 효율적이겠구나" 라는 직관이 오실 때까지 연습해보시는 것이 좋습니다.

그러면 이 문제를 푸시느라 수고 많으셨습니다!

# 결과 코드

def solution(board, moves):
    bucket = []
    answer = 0
    
    for move in moves:
        index = move - 1
        for row_info in board:
            if row_info[index] != 0:
                bucket.append(row_info[index])
                row_info[index] = 0
                if len(bucket) >= 2 and bucket[-1] == bucket[-2]:
                    answer += 2
                    bucket = bucket[0:-2]
                break
    return answer

🤗 3. 끝내며

혹시 더 나은 풀이나 잘못된 부분이 있다면 댓글로 남겨주세요

오늘도 좋은 하루 보내시길 바랍니다