본문 바로가기

About/Algorithm

[프로그래머스][C++] 크레인 인형뽑기 게임(카카오 2019 개발자 겨울 인턴십 문제)

출처 : 프로그래머스

https://programmers.co.kr/

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제를 간단하게 설명하면 N * N인 배열에서 인형 뽑기 하듯 선택된 열에서 가장 높은 행의 값을 가져와서 바구니에 세로로 담는데 바구니의 맨 위에 있는 인형의 값과 새로 담는 인형의 값이 같은 경우 인형이 사라지게 된다.

e

사라진 인형의 갯수를 return 하면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> picked_dolls;
    int picked_doll = 0;
    int index = 0;
    for (int move = 0; move < moves.size(); move++) {
        picked_doll = 0;
        index = moves[move] - 1;
        for (int row = 0; row < board.size(); row++) {
            if (board[row][index] == 0)
                continue;
            else {
                picked_doll = board[row][index];
                board[row][index] = 0;
                break;
            }
        }
        if (picked_doll != 0) {
            if (!picked_dolls.empty() &&picked_dolls.back() == picked_doll) {
                answer = answer + 2;
                picked_dolls.pop_back();
            }
            else
                picked_dolls.push_back(picked_doll);
        }
    }
    return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

vector<int> picked_dolls;

picked_dolls라는 vector를 만들어 바구니로 사용하였다.

 

move vector에 뽑을 열들이 되어있기 때문에 f

moves 벡터에서 하나씩 뽑아오도록 for문을 작성하였고

배열에선 0부터 되어있기 때문에 -1을 해주어서 index를 만들어주었다.

 

그 후 행을 조사하는데 board[row][index] 값이 0이면 빈 값이기 때문에 continue 해주었고

0이 아닐 경우 picked_doll에 저장해주고 board [row][index]를 빈 값으로 만들어 주었다.

  for (int move = 0; move < moves.size(); move++) {

        picked_doll = 0;

        index = moves[move] - 1;

        for (int row = 0; row < board.size(); row++) {

            if (board[row][index] == 0)

                continue;

            else {

                picked_doll = board[row][index];

                board[row][index] = 0;

                break;

            }

        }

그 후 picked_doll이 0이 아닐 경우 ( 해당 열에 아무 인형도 없었을 경우 값이 0 임)

picked_doll의 벡터를 조사한다.

picked_doll 벡터가 비어있지 않고, picked_doll의 마지막 값이 현재 인형의 값과 같으면

인형을 2개 없앨 것 이기 때문에

answer에 2를 더해주고

picked_doll을 pop_back() 해준다. (스택 동작)

   if (picked_doll != 0) {

            if (!picked_dolls.empty() &&picked_dolls.back() == picked_doll) {

                answer = answer + 2;

                picked_dolls.pop_back();

            }

            else

                picked_dolls.push_back(picked_doll);

        }

}

 

이 작업을 모든 move에 대해서 반복해주면 답이 된다.