프로그래머스 크레인 인형 뽑기 from kakao (Python)

임동혁 Ldhbenecia·2024년 2월 16일

구현 알고리즘 프로그래머스

Algorithm

목록 보기

10/16

프로그래머스 크레인 인형 뽑기 from kakao

💡 3월 중순 이후부터 알고리즘을 더 공부하고 그 전까지는 간단한 문제를 풀기 위해 레벨 1 문제를 풀이한다. 2019 카카오 개발자 겨울 인턴십 문제이다.

정답 코드

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

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

        if len(basket) >= 2 and basket[-1] == basket[-2]:
            answer += 2
            basket = basket[:-2]
                
    return answer

풀이과정

전형적인 스택을 사용하면 풀 수 있는 풀이이다.
살짝 처음에 어려웠던 점은 2차원 리스트에서 추출해야할 값을 어떻게 뽑아내야할 지에 대해서 생각했다.

이 예시를 가지고 풀이를 해보면

moves가 1
4를 추출하고 이는 board[4][0]
moves가 5
3을 추출하고 이는 board[1][4]
moves가 3
1을 추출하고 board[2][2]

여기서 알 수 있는 점은 두번째 좌표의 값은 moves - 1이라는 것이다.
그리고 이전의 값은 규칙성을 찾지 못했다.

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

board의 길이는 5로 0부터 4를 가지고 반복문을 시작한다.
1. moves가 1일 경우
0 0 0 4 3
2. 5일 경우
0 3 1 2 1

for문을 위와 같이 돌기 시작하면
board[j][i-1]은
board[0][0]
board[1][0]
board[2][0]
board[3][0]
board[4][0]

moves = 5 - 1
board[0][4]
board[1][4]
board[2][4]
board[3][4]
board[4][4]

이러한 형태꼴이 나오기 때문에 해당 값을 가져올 수 있다.
그 후는 정말 간단하다.

0인 경우는 아무것도 처리할 것이 없으니 0보다 크면 해당 값을 뽑았으니
basket이라는 리스트에 넣어준다.
그 후 그 자리는 비었으니 0으로 변경한다.
그리고 다음 값이 0이 아니면 또 넣게 되는데 제일 위의 값을 뽑았으면 다음 moves로 넘어가야하니 break를 통해 for문에서 탈출한다.

basket에 넣은 가장 마지막 값이 이전에 넣은 값과 같다면 인형이 터진다.
터지게 되면 2개가 터지게 되니 +=2를 해주고 basket의 값은 끝에서 두 개를 지운 항목들만 남기면 끝난다.

처음에 index 오류가 나서 basket의 길이가 2개 이상일때의 조건도 걸어주었다.

len(basket) > 2로만 하면 테스트케이스 1, 2번만 실패한다.
이상으로 표시를 하지 않아서 수정 후 바로 정답이 되었다.