[프로그래머스] 크레인 인형뽑기 게임 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

본 문제는 프로그래머스의 크레인 인형뽑기 게임 문제입니다.

n x n 크기의 정사각 격자에 인형이 들어가고 인형은 아래서 부터 위로 쌓입니다.

인형은 위에서부터 뽑을 수 있고 뽑히는 칸의 순서는 배열로 주어집니다.

그리고 바구니가 하나 있고 크레인으로 뽑은 인형들을 이 바구니에 담습니다.

바구니의 특성 상 한 층에 하나의 인형 밖에 못 두어 인형이 하나씩 쌓이게 됩니다.

이 때 같은 인형이 두 개만나면 이 두 인형을 없애며 없앤 인형의 갯수를 최종적으로 반환하여야 합니다.

 

문제 출처 :

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

 

 

해결 과정

 

격자배열 전체를 순회하여 가장 상단에 존재하는 값만을 tops라는 배열에 저장합니다.

이후 인형을 뽑는 순서가 적힌 배열을 순회하여 해당 칸의 상단값을 tops에서 가져와

stack에 저장하고 stack 저장될 때 마다 전의 상단값과 비교해 같다면 이를 지워주고

없앤 인형의 수를 반환하기 위해 answer에 2를 더해줍니다.

tops에서 가져온 뒤에는 기존 상단값에서 높이가 한 칸 아래인 값으로 대체해줍니다.

이 때문에 따로 height 값을 같이 저장하는데 그래서 tops는 vector<pair<int, int>>로

만들었습니다.

 

 

 

코드 전문

 

 

#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <utility>

using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> stk;
    vector<pair<int, int>> tops;
    
    // tops initialize
    for (int pos = 0; pos < board.size(); pos++)
    {
        for (int height = 0; height < board.size(); height++)
        {
            if (board[height][pos] != 0)
            {
                tops.push_back({board[height][pos], (board.size()-1)-height});
                break;
            }
            if (height == board.size()-1 && board[height][pos] == 0) tops.push_back({0, 0});
        }
    }

    stk.push(-1);
    for (auto move : moves)
    {
        if (tops[move-1].first != 0)
        {
            if (stk.top() == tops[move-1].first)
            {
                stk.pop();
                answer+=2;
            }
            else stk.push(tops[move-1].first);

            if ((tops[move-1].second) > 0)
            {
                tops[move-1] = {board[(board.size())-tops[move-1].second][move-1], tops[move-1].second-1};
            }
            else tops[move-1] = {0, 0};
        }
    }

    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

첫단추를 잘 꿰야한다는 생각을 하게 되었습니다. 처음에 아이디어를 얻고 시도를 하였는데, 진행하면서

height도 따로 저장해 다뤄야하는구나를 깨달고 매번 tops를 바꾸기 위해 한 눈에 봐도 알기 어려운 코드가

만들어졌습니다. pair 상당히 좋아했는데 두 값의 접근을 위해 사용하는 first와 second가 이름으로써 역할을

알린다는 네이밍의 목적을 발휘 못하는데 있어서 아쉬움이 있었습니다. 

제가 만든 코드에 비해 다른 분들이 만들어 주신 코드는 정말 깔끔했습니다. 보고 배워야겠습니다.

정말 코드를 잘 짜는 사람은 어렵게 접근해서 어려운 코드를 만드는게 아니라

어렵게 접근하더라도 최대한 알아보기 쉬운 코드를 짜는 것 같습니다.

전 항상 문제를 해결하기 위해 하나부터 열까지의 모든 순수 과정을 그대로 구현하려는 습관이 있는 것 같습니다.

많이 풀어봐야겠어요.

그리고 2차원 배열도 써봤네요. 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.