[프로그래머스 64061] - 카카오 기출 크레인 인형뽑기 게임

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/64061

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

 

문제풀이

아마 처음 긴장을 풀어주기 위해 1번 문제로 준비한 문제가 아닐까 싶다. 이 문제에서의 핵심은 스택을 사용하는 거라 생각한다. 바구니는 아래칸부터 인형이 순서대로 쌓이는 구조이며 이는 한쪽에서만 입력이 일어남을 알 수 있다. 크레인이 인형을 뽑고나서 스택의 top과 뽑은 인형이 같다면 스택을 pop하고 정답을 2 더해주면 되는 문제이다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%EA%B2%8C%EC%9E%84.cpp

sw93/algorithm

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    for (int i=0; i<moves.size(); i++) {
        int x = moves[i] - 1;
        
        for (int y=0; y<board.size(); y++) {
            if (board[y][x] == 0) continue;

            if (!s.empty() && (s.top() == board[y][x])) {
                s.pop();
                answer += 2;
            } else {
                s.push(board[y][x]);
            }
            
            board[y][x] = 0;
            break;
        }
    }
    return answer;
}