Level 1 크레인 인형뽑기 게임 <2019 카카오 인턴> Python 3

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

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level1_크레인인형뽑기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(board, moves):
    answer = 0
    stack = []
    for m in moves:
        for row in range(len(board)):
            if board[row][m-1] != 0:
                if len(stack) > 0:
                    if stack[-1] == board[row][m-1]:
                        answer += 2
                        stack.pop()
                    else: stack.append(board[row][m-1])
                else: stack.append(board[row][m-1])
                board[row][m-1] = 0
                break
    return answer

---

풀이 과정

풀이 시간 20분

 

def solution(board, moves):
    answer = 0
    stack = []
    for m in moves:
    	#m-1열의 인형이 있는 행 찾기
        for row in range(len(board)):
        	#뽑을 인형을 찾은 경우
            if board[row][m-1] != 0:
            	#stack이 비어있지 않은 경우
                if len(stack) > 0:
                	#stack의 top에 있는 인형과 현재 뽑으려는 인형이 같은 경우
                    if stack[-1] == board[row][m-1]:
                    	#stack의 top에 있는 인형과 현재 뽑으려는 인형이 사라진다
                        answer += 2
                        stack.pop()
                    
                    #stack의 top에 있는 인형과 현재 뽑으려는 인형이 다른 경우, stack에 인형을 쌓는다
                    else: stack.append(board[row][m-1])
               
               	#stack이 비어있는 경우, stack에 인형을 쌓는다   
                else: stack.append(board[row][m-1])
                
                #인형을 뽑았으므로, 빈 칸으로 표현한다
                board[row][m-1] = 0
                break
    return answer
#시간복잡도 = O(len(moves)*len(board)) = O(n), 공간복잡도 = O(n)

---

참고

• 2. 튜플 ->2021.09.06 - [코테 노트/프로그래머스] - Level 2 튜플 <2019 카카오 인턴십> Python 3

Level 2 튜플 <2019 카카오 인턴십> Python 3

• 3. 불량 사용자 -> https://hwayomingdlog.tistory.com/144

Level 3 불량 사용자 <2019 카카오 개발자 겨울 인턴십> Python 3

• 4. 호텔 방 배정 -> 
• 5. 징검다리 건너기 -> https://hwayomingdlog.tistory.com/154

Level 3 징검다리 건너기 <2019 카카오 인턴십> Python3