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

ziwon.k·2021년 5월 3일

C 알고리즘 카카오 코테 프로그래머스

[프로그래머스] 연습문제

목록 보기

9/10

프로그래머스 - Lv1.크레인 인형뽑기 게임(2019 카카오 개발자 겨울 인턴십)

1.문제

2.접근/체크 포인트

인형을 뽑아서 보관할 스택 필요.

board 배열이 행 기준으로 주어지지만, 뽑기는 열 기준으로 해야함.

moves에서 주어진 index 주의하기. (moves의 1은 board의 0)

3.해결 방법

moves 원소 수 만큼 반복하면서 인형을 뽑는다.

이때, 해당 열에 인형이 있는지 (0이 아닌지) 확인 후, 인형이 있다면 뽑기 가능.

인형을 뽑기 전, 뽑은 인형을 보관할 스택에 인형이 있는지 없는지 확인한다.

스택에 인형이 없다면 바로 인형을 뽑아 스택에 넣고(터질 인형이 없으므로), borad에서 해당 칸을 0으로 변경한다.

스택에 인형이 있다면 지금 뽑을 인형이랑 같은 인형인지 확인한다.

같은 인형이라면 인형을 터트려야 함! (answer +=2), 스택의 최상단 인형을 pop 시키고, board 에서도 0으로 변경한다.

스택에 있는 인형이 같은 인형이 아니라면 그냥 스택에 넣고, borad에서 0으로 변경한다.

각 케이스 별로 인형을 뽑은 뒤 break 처리를 꼭 해줘야한다. (인형은 한번에 하나만 뽑을 수 있기 때문)

4. 전체 코드

#include <string>
#include <vector>
#include <stack>
#include<iostream>
using namespace std;


int answer = 0;


int solution(vector<vector<int> > board, vector<int> moves) {

    
    stack<int> doll;  //인형을 뽑아서 보관할 stack
    
    for(int i = 0; i<moves.size(); i++){
        for(int j=0; j<board.size(); j++){

            //board판에 인형이 있으면 뽑아야함
            if(board[j][moves[i]-1] != 0){ 

               //스택에 인형이 없으면 같은지 검사 안하고 바로 스택에 넣을 수 있음
                if(doll.empty()){
                    doll.push(board[j][moves[i]-1]); //뽑아서 stack에 넣고
                    board[j][moves[i]-1] = 0;        //board에서 뽑기 처리
                    break;                           //한 번에 인형 하나씩 뽑을 수 있음
                }else{ //스택에 이미 인형이 있다면
                       //스택에 넣기 전에 스택의 최상단에 같은 인형이 있는지 확인해야함
                       //같은 인형이 있으면 
                    if(doll.top() == board[j][moves[i]-1]){
                        answer +=2;           //같은 인형이면 터트리기, 2개씩 터지니까 +2
                        doll.pop();           //stack에서 터진 인형 빼기
                        board[j][moves[i]-1] = 0;          //board에서 뽑기 처리
                        break;
                    }else{
                        //같은 인형이 없으면 그냥 넣기
                        doll.push(board[j][moves[i]-1]);  //뽑아서 stack에 넣고
                        board[j][moves[i]-1] = 0;         //board에서 뽑기 처리
                        break;                      

                    }
                }
            }else{
                continue;  //인형이 없으면 pass
            }
        }
    }
    return answer;
}//end of solution

5.참고사항

👉 Stack 사용시 stack 헤더파일을 포함해줘야 함.
#include<stack>

👉 Stack 관련 함수 정리

s.push(2); 스택에 2(값) 추가.

s.pop(); 스택의 최상단 원소 제거

s.top(); 스택의 최상단 원소 반환

s.size(); 스택의 크기 반환

s.empty(); 스택이 비어있으면 true

s.swap(s1); 스택 s1과 원소 바꾸기

6.다른 방법으로 풀어보기

행을 기준으로 주어지는 board를 열을 기준으로 변경해서 푸는 방식

function grabDolls(transposedBoard, moves){
    let vanishedDolls = 0; // 사라진 총 인형의 수
    let stackedDolls = []; // 뽑혀서 쌓인 인형의 배열
    
    moves.map((move) => {
        // 쌓인 인형의 수
        let stackedDollsCount = stackedDolls.length;
      	// 만일 집게가 간 열에 인형이 존재한다면, (인형이 없을 수 있음)
        if(transposedBoard[move-1].length > 0){
            // 집게에 잡힌 인형은 첫번째 인형
            let grabbedDoll = transposedBoard[move-1].shift();
            // 쌓인 인형이 있고, 맨 위에 쌓인 인형이 집게에 잡힌 인형과 같은 인형이라면 쌓인 인형 없애기
            if(stackedDollsCount > 0 && 
                stackedDolls[stackedDollsCount-1] 
                === grabbedDoll){
                stackedDolls.pop();
                // 인형은 한번에 2개씩 사라지기 때문에 2개 더하기
                vanishedDolls += 2;
            }else {
                // 만일 쌓여있던 인형과 일치하지 않으면 인형을 그냥 쌓기
                stackedDolls.push(grabbedDoll);
            }
        }
    });

    // 총 사라진 인형이 정답
    return vanishedDolls;
}

코드 출처