Lv1_[크레인 인형뽑기 게임, C++] 알고리즘 정리 - 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

문제의 핵심은 "2차원 배열 되어 있는 보드판과 크레인이 움직일 때 어떤 차원의 인덱스를 증가시켜줄 수 있는지"를 보는 문제이다.

 

예를들어 3X3 Board에서 move 2번이 들어온다면 크레인을 위의 그림과 같이 배치가 된다.

1) move 2번이지만 board index는 0부터 시작하기 때문에 -1을 해줘서 1번째 위치에서 시작

2) 1차원 index는 고정되고 2차원 index의 값을 변경하면서 인형을 찾음

 

그 뒤 동작은

1) 인형을 뽑음

2) 뽑은 위치를 빈값으로 만들어 줌

3) 뽑은 인형을 바구니에 옮김

4) 바구니 맨 뒤에 인형과 뽑은 인형이 같은지 비교

  4-1) 같으면 바구니의 맨끝 인행을 제거 후 결과에 +2

  4-2) 다르면 바구니에 인형 저장

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int appered_count = 0;
    vector<int> bakkess;
 
    
    for (auto item : moves) {
        int pick_index = item - 1;  // moves의 기준이 1이기 때문에 -1을 해줌
        int find_item = 0;
 
        for (int i = 0; i < board.size(); i++) {
            int &found_column_item = board[i][pick_index];  // 값 변경을 위해 참조자로 선언
            if (found_column_item != 0) {
                find_item = found_column_item;
                found_column_item = 0;        // 찾은 항목은 0으로 변경
                break;
            }
        }
 
        if (find_item != 0)    {
            // 2. 뽑아온 항목과 바구니 맨끝에 저장되어 있는 항목과 비교
            int bakkess_size = bakkess.size();
            if (bakkess_size > 0) {
                if (*(bakkess.end() - 1) == find_item) {    // 같은면 터트리기
                    bakkess.erase(bakkess.end() - 1);
                    appered_count += 2;        // 터트린 인형 수 추가
                } else {    // 다르면 추가
                    bakkess.push_back(find_item);    
                }
            } else {
                bakkess.push_back(find_item);
            }
        }
    }
 
    return appered_count;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓