[프로그래머스] 크레인 인형뽑기 게임 C++ (Lv.1)

 

 

 

 

 

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

프로그래머스

 

이번 문제는 2019 카카오 개발자 겨울 인턴십 문제였습니다.

 

 

 

 

 

 

📝 문제 풀이

1. 각 위치에서 가장 위에 있는 인형의 좌표를 담을 doll 벡터 선언 

   vector<pair<int, int>> doll(board[0].size() + 1, {-1, -1}); ⬅️ 위치는 1부터 시작하므로 board[0].size() + 1

2. 각 위치에서 가장 위에 있는 인형의 좌표 담기 (빈 칸이 아니면 인형이 들어있는 칸) ⭐️

3. moves 벡터의 각 위치에 대해 가장 위에 있는 인형과 바구니에 담긴 인형(stack.top())이 같은 모양의 인형이면 answer += 2

4. 각 위치의 가장 위에 있는 인형의 좌표를 뽑은 인형의 아래 칸 좌표로 갱신

 

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    vector<pair<int, int>> doll(board[0].size() + 1, {-1, -1});
    
    // 각 위치에서 가장 위에 있는 인형의 좌표 담기
    for (int i=0; i<board[0].size(); i++) {
        for (int j=0; j<board.size(); j++) {
            if (board[j][i] != 0) {
                doll[i + 1] = {j, i};
                break;
            }        
        }
    }
    
    for (int m: moves) {
        // 인형이 없는 곳에서는 아무런 일도 일어나지 않음
        if (doll[m].first == -1) continue;
        
        // 바구니에 담긴 인형과 같은 모양의 인형이면 두 인형은 터트려짐
        if (!s.empty() && s.top() == board[doll[m].first][doll[m].second]) {
            answer += 2;
            s.pop();
        } else {
            s.push(board[doll[m].first][doll[m].second]);
        }
        
        // 가장 아래 칸이 아니면 아래 칸의 인형의 좌표 담기
        if (doll[m].first < board.size() - 1) doll[m] = {doll[m].first + 1, doll[m].second};
        else doll[m] = {-1, -1}; // 가장 아래 칸이면 더 이상 집을 인형이 없음
    }
    
    return answer;
}

 

프로그래머스 - 결과 화면