[프로그래머스] 크레인 인형뽑기 게임

 

 

문제

소스코드

#include<iostream>
#include<vector>
#include <string>
#include<stack>
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
 
    //Stack 형식으로 재배열
    std::vector<std::stack<int>> stackBoard(board.size());
    for (int j = 0; j < board.size(); ++j) {
        for (int i = board.size() - 1; i >= 0; --i) {
            if(board[i][j]!=0)
            stackBoard[j].push(board[i][j]);
 
        }
    }
 
    //넣을 스텍
    std::stack<int> s;
 
    // 포인터는 해당 스텍을 가리키는 포인터이며
    // FIFO 특성을 가진 Stack을 이용하여 배열에 넣는다.
    for ( auto& pointer : moves) {
        //index와 호환을 위한 -1
        pointer -= 1;
 
        if (stackBoard[pointer].empty())
            continue;
 
        auto topValue = stackBoard[pointer].top();
        stackBoard[pointer].pop();
 
        //스텍이 비어있는 상태가 아니고 현재 스텍과 넣을 값이 같다면 터트리고 +=2
        if (s.empty() == false && s.top() == topValue) {
            s.pop();
            answer += 2;
        }
        //아니라면 그냥 스텍에 넣는다.
        else {
            s.push(topValue);
        }
    }
 
    return answer;
}

 

 

후기

 

이 문제를 해결하기 위한 키워드는 Stack(스택)이다.

 

나는 이 문제를 풀기 위해 먼저 입력으로 들어오는 Vector를 0을 제외한 Stack형식으로 다시 재배열해서 하나의 자료구조를

만들었다. 그 자료구조가 stackBoard이다.( 꼭 이렇게 안 해도 기존 꺼로도 풀이가 가능하다.)

 

그 다음 이 stackBoard 이하 스택 보드를 이용해서 moves 입력값에 있는 숫자를 가지고 하나씩 꺼냈으며 std::<stack> s 라는 스택 자료구조에 값을 넣었다. 여기서 이 s는 문제에서 말하는 바구니이다. 집어넣을 때에는 이 바구니 스택이 비어있는지 확인하고 비어있지않다면 현재 최상단 바구니 값과 스택 보드의 값을 비교해서 같다면 바구니 스택의 값을 pop 하고 +=2를 했으며 그 외에는 바구니 스택에 값을 넣는 형식으로 풀었다.

 

 

 

출처 및 레퍼런스

문제 링크: programmers.co.kr/learn/courses/30/lessons/64061

 

관련 글

[온라인 코딩/큐(Queue)와 스택(Stack)] - [백준] 10828번 스택

[자료구조 알고리즘/큐(Queue)와 스택(Stack)] - [Stack] 간단한 Stack 구현