[프로그래머스/C++] ㅡ LV1 - 크레인 인형뽑기 게임

문제

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

코딩테스트 연습 - 크레인 인형뽑기 게임

풀이

#include <vector>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    stack<int> s;
    int cnt = 0;
    for (int i=0; i<moves.size(); i++) {
        int x = moves[i]-1;
        for (int j=0; j<board.size(); j++) {
            int y = board[j][x];
            if (y !=0) {	// 인형 존재함
                if (!s.empty() && s.top() == y) {	// 인형 연속으로 쌓임
                    board[j][x] =0;
                    s.pop();
                    cnt+=2;
                }
                else {		// 인형 연속 아님
                      s.push(y);
                      board[j][x] =0;
                }
                break;
            }
        }
    }
    return cnt;
}

개념

프로그래머스에서는 입력 받는 부분 코드를 작성하지 않아도 된다.

solution 함수에 인수로 들어오는 값이 입력이다.

 

int main() {

    solution(입력);

    return 0;

}

 

 

이렇게 생각하면 간단한 것 같다.

---

vector<int> moves 는 일차원 배열, vector<vector<int>> board 는 이차원 배열이다.

 

board.size() 는 board[x][y] 에서 x인 행의 크기를 의미한다.

board[x].size() 는 이제 board[x]의 y인 열의 크기이다.

 

if (!s.empty() && s.top() == y) 에서 !s.empty()를 꼭 넣어야한다.

s 스택이 empty일 때 s.top()을 참조하는 것은 에러를 유발한다.

 

---

풀이

 

일단 선입후출(FIFO)이므로 stack을 사용하기로 생각했다.

 

2중 반복문을 통해 탐색하는 과정이다.

 

반복문

moves 배열의 크기만큼 크레인 사용을 반복한다.

x를 정의하여 각 moves 의 배열에 존재하는 값을 대입한다. (배열값은 0부터 시작이므로 moves[]-1을 하였다)

 

반복문

board의 행의 크기만큼 탐색을 반복한다.

y를 정의하여 해당 행의 x열 값을 대입한다.

 

if문

y가 0이면 다음 행을 탐색하며, 인형이 없는 곳에서는 아무일도 일어나지 않는다.

 

if문

y가 0이 아닐 때, 2가지 케이스로 나뉜다.

 

①스택 맨 위 값이 y와 같음

②그렇지 않음

 

1의 경우 스택에서 값을 빼주고 cnt에 +2를 한다.

2의 경우 스택에 새로운 값을 넣어준다.

 

y가 아닌 경우 다음 탐색이 진행될 필요가 없다.

따라서 둘다 break를 사용한다.