[프로그래머스] 크레인 인형 뽑기 | C++

문제

프로그래머스

 

 

크레인의 위치가 주어지면

board 안에 있는 인형을 바구니로 옮겨담아서

바구니 안에 연속으로 같은 인형이 담기면 갯수를 더하는 문제였다.

 

나의 풀이 전략

1. 크레인의 위치에 따라 인형을 뽑고 바구니에 옮겨담는 PickandDrop()이란 함수를 만들었다.

PickandDrop()에서 인형의 갯수도 세어나갈 것이다.

2. solution()에 인수로 주어진 moves를 따라 PickandDrop()을 실행한다.

 

상세

1. PickandDrop()은 인형의 나열정보(board)와 크레인의 위치(move)를 입력받도록 설정한다.

void PickandDrop(vector<vector<int>>& board, int move)
{
	
}

 

2.  크레인의 위치정보(Crane)를 만들고, 인형을 찾을 때까지 크레인을 내리도록 한다.

void PickandDrop(vector<vector<int>>& board, int move)
{
    pair<int, int> Crane = make_pair(0, move - 1);

    while(board[Crane.first][Crane.second] == 0)
        Crane.first += 1;
}

 

3. 그런데 주의할 점이 있다.

크레인이 인형을 못 찾고 board를 넘어 가버릴 수도 있다.

이를 방지하기 위해 크레인에 제약조건을 추가해주어야 한다.

 

필자는 다음과 같이 했다.

크레인의 다음 줄이 board의 맨 마지막 줄보다 작거나 같게 하였다.

(이렇게 하면 미리 체크하는 듯한 안도감이 들기 때문이었다.)

Crane.first + 1 <= board.size() - 1

 

void PickandDrop(vector<vector<int>>& board, int move)
{
    pair<int, int> Crane = make_pair(0, move - 1);

    while(Crane.first + 1 <= board.size() - 1 &&
    		board[Crane.first][Crane.second] == 0)
        Crane.first += 1;
}

 

4. 이제 크레인이 인형(또는 빈 공간)까지 내려갔다.

인형의 종류(doll)를 저장하도록 해주자.

인형종류를 저장하면 해당 위치를 빈 공간으로 저장해야 한다.

void PickandDrop(vector<vector<int>>& board, int move)
{
    // ...

    int doll = board[Crane.first][Crane.second];
    board[Crane.first][Crane.second] = 0;
}

doll에는 인형이 아닌, 빈 공간(0)이 저장될 수도 있다는 점을 주의해주자.

 

5. 인형정보를 저장했으면 바구니에 옮겨담을 차례다.

바구니를 스택으로 구현하자.

필자는 PickandDrop()에 인수를 늘리기 싫어서 그냥 전역에 객체(Basket)로 만들어두었다.

stack<int> Basket; // 바구니

void PickandDrop(vector<vector<int>>& board, int move)
{
    // ...
}

 

6. PickandDrop()을 여러차례 수행하다보면 바구니에 인형들이 들어있을 수 있다.

바구니 맨 위의 인형과 새로 뽑은 인형이 같다면 정답(res)에 더해주도록 하자.

res 역시 전역에 두었다.

stack<int> Basket;
int res = 0; // 우리가 반환할 정답

void PickandDrop(vector<vector<int>>& board, int move)
{
    // ...
	
    if (Basket.size() && Basket.top() == doll)
    {
        res += 2;
        Basket.pop();
    }
}

 

7. 바구니에 인형이 없거나 맨 위의 인형과 같지 않다면 그냥 바구니에 넣어주자.

이 때, doll에는 인형이 아닌 빈 공간(0)일 수도 있다고 하였다.

빈 공간이 들어가지 못하도록 제약조건(if)을 넣어주자.

void PickandDrop(vector<vector<int>>& board, int move)
{
    // ...
	
    if (Basket.size() && Basket.top() == doll)
    {
        res += 2;
        Basket.pop();
    }

    else
        if(doll) Basket.push(doll);
}

 

8. 완성한 PickandDrop() 함수를 solution에서 실행해준다.

answer에는 전역에 둔 res를 그대로 받도록 한다.

void PickandDrop(vector<vector<int>>& board, int move)
{
    // ...
}

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;

    for(int move : moves)
        PickandDrop(board, move); // 우리가 작성한 함수

    answer = res;

    return answer;
}

 

전체 소스코드

#include <bits/stdc++.h>
using namespace std;

stack<int> Basket;
int res = 0;

void PickandDrop(vector<vector<int>>& board, int move)
{
    pair<int, int> Crane = make_pair(0, move - 1);

    while(Crane.first + 1 <= board.size() - 1 &&
    		board[Crane.first][Crane.second] == 0)
        Crane.first += 1;

    int doll = board[Crane.first][Crane.second];

    board[Crane.first][Crane.second] = 0;

    if (Basket.size() && Basket.top() == doll)
    {
        res += 2;
        Basket.pop();
    }

    else
        if(doll) Basket.push(doll);
}

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;

    for(int move : moves)
        PickandDrop(board, move);

    answer = res;

    return answer;
}

int main() {
    cout << solution({{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0,0}}, {1,2,3,4});
    return 0;
}