python | 카카오 크레인 인형 뽑기

yeeun lee·2020년 6월 28일

프로그래머스에 올라온 카카오 개발자 겨울 인턴십 코테 문제를 풀어보았다. 가장 쉬운 문제라는(...) 크레인 인형 뽑기 게임을 파이썬으로 풀었는데, 문제를 초반에 어렵게 접근해서 애를 먹었다 😞

문제

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

첫 번째 접근

처음에는 아래와 같이 접근했다.

2차원 배열에서 index를 잡아주고
index value가 0이 아니면 bucket에 넣은 뒤
bucket에 인형이 다 쌓이면 인접한 숫자끼리 제거하는 식의 로직

아래 문제는 배열이 5x5 사이즈일 때는 통과가 되는데, 정답을 제출하면 다른 많은 문제에서 실패가 뜬다.

처음에 for i in rage(10)이 0부터 10까지라고 착각해서 len(board)에서 -1를 해주려고 했다. 근데 자꾸 index out of range error가 떠가지구 찾아보니까... 0부터 10번째까지 ( = 9번째 인덱스까지) 돌리는거였다.

# 실패 
def solution(board, moves):
    bucket = []
    for move in moves:
        for i in range(len(board)):
        
            # moves 배열의 값들이 1부터 시작하는 자연수로 되어있기 때문에 move-1
            # 인덱스로 쓰기 위해서는 0~n 형태여야 하기 때문에 -1를 빼줌
            if board[i][move-1] > 0:
                bucket.append(board[i][move-1])
                board[i][move-1] = 0
                
                # 0이 아닌 숫자를 찾으면 두 번째 for loop를 나와야 함
                # 안 나오면 더 밑에 있는 인형까지 주워올 수 있으니 주의! 
                break
                
    answer = [] 

    # 시작점을 1로 설정하고, 같은 인형이 나올 때마다 해당 인형을 빼준 뒤에 
    # 다시 버켓의 처음으로 돌아갈 수 있도록 
    i = 1
    while i < len(bucket):
        if bucket[i-1] == bucket[i]:
            answer.append(bucket[i])
            bucket.remove(bucket[i])
            bucket.remove(bucket[i-1])
            i = 1
        else:
            i += 1
    return len(answer)*2

그런데 1,2,3,5번만 통과하고 계속 다른 것은 실패했다 😭😭😭😭
처음에는 이유를 몰라서 그냥 다른 방법을 찾았는데, 만약 같은 인형이 2개 이상으로 중복된다면?이 갑자기 생각났다! 그러니까 같은 인형이 엄~청 많이 나올 수 있는건데, 내가 짠 코드는 예시에서 두 개의 인형이 중복될 때만 생각한 것이다.... (바보)

두 번째 접근

애초에 버켓에 넣을 때 가장 마지막 것과 비교해서 빼주면 불필요한 반복문(심지어 무한 루프에 빠질 수 있는 while)을 쓰지 않아도 되기 때문에, 코드의 복잡도가 훨씬 더 감소한다.

아래 코드로 다시 짜보니 바로 통과가 좌르륵 떠서 뿌듯했당 💕

# 성공!
def solution(board, moves):
    bucket = []
    answer = []
    for move in moves:
        for i in range(len(board)):
            if board[i][move-1] > 0:
                bucket.append(board[i][move-1])
                board[i][move-1] = 0
                if bucket[-1:] == bucket[-2:-1]:
                    answer += bucket[-1:]
                    bucket = bucket[:-2]
                break
    return len(answer)*2