반갑습니다!

[프로그래머스] 크레인 인형뽑기 게임 본문

알고리즘 문제 풀이

[프로그래머스] 크레인 인형뽑기 게임

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

풀이

바구니를 stack으로 구현하면 되는 문제이다. 인형을 집고 떨어뜨리기 전에 stack의 가장 위에 있는 인형의 종류를 확인하여 같은 인형이면 pop해주면 된다.

코드

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;
    for(int i=0; i<moves.size(); i++){
        int pick = moves[i] - 1;
        int h = 0;
        while(h < board.size() && board[h][pick] == 0) h++;
        if(h < board.size() && board[h][pick] != 0){
            if(!s.empty() && s.top() == board[h][pick]) {
                answer += 2;
                s.pop();
            }
            else s.push(board[h][pick]);
            board[h][pick] = 0;
        }
    }
    return answer;
}


Java

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        int n = board.length;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < moves.length; i++) {
            int x = moves[i] - 1;
            for (int y = 0; y < n; y++) {
                if (board[y][x] != 0) {
                    int doll = board[y][x];
                    board[y][x] = 0;
                    if (!stack.empty() && stack.peek() == doll) {
                        stack.pop();
                        answer += 2;
                    } else {
                        stack.push(doll);
                    }
                    break;
                }
            }
        }
        return answer;
    }
}