[programmers] 프로그래머스 크레인 인형뽑기 게임(C++, Python)

(주)그렙

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

(C++, Python)

(글쓴날 : 2020.05.08)

 

---

* programmers, 프로그래머스 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

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

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

N X N 크기의 2차원 배열에 인형으로 가정한 각기 다른 숫자들이 들어있고, 인형들을 주어진 조건에 맞추어 배열에서 꺼내 바구니에 저장할 때, 바구니에서 사라지는 인형의 개수를 구하는 문제입니다.

 

저의 경우, C++와 Python을 사용했습니다.

인형이 들어있는 배열을 열기준으로 탐색해가며 발견된 인형을 스택으로 구현한 바구니에 저장하였고,

만약, 같은 인형이 push될 경우 답을 2 증가시키고 pop을 2번 하는 식으로 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int answer = 0;
    int m = 0;
    
    stack<int> s;
    s.push(0);
    
    int beforeNum = 0;
    bool isPush = false;
    
    for (int i = 0; i< moves.size();i++) {
        m = moves[i];
        isPush = false;
        
        for (int j =0; j<board[0].size();j++) {
            if (board[j][m-1] != 0) {
                isPush = true;
                s.push(board[j][m-1]);
                board[j][m-1] = 0;
                break;
            }
        }
        
        if (isPush && s.top() == beforeNum) {
            s.pop();
            s.pop();
            answer+=2;
        }    
 
        beforeNum = s.top();
    }
    
    return answer;
}

---

* Python 코드

def solution(board, moves):
    answer = 0
    stack = [0]
    
    for m in moves:
        isPush = False
        for j in range(len(board[0])):
            if board[j][m - 1] != 0:
                isPush = True
                stack.append(board[j][m - 1])
                board[j][m - 1] = 0
                break
        
        if isPush and stack[-1] == stack[-2]:
            answer += 2
            stack.pop()
            stack.pop()
        
    return answer

---