[Programmers 알고리즘, C++]#Level1_크레인 인형 뽑기, 2차원 배열, stack, STL 컨테이너, adjacent_find()

[Programmers 알고리즘, C++]#Level1_크레인 인형 뽑기, 2차원 배열, stack, STL 컨테이너, adjacent_find()

 

Programmers 알고리즘 문제 풀이, Level1_크레인 인형뽑기

2차원 배열의 개념과 STL 컨테이너 활용 문제

 

---

 

문제

풀이

 

문제는 스택 자료구조에대한 이해와 2차원 배열의 활용을 요구합니다.

 

먼저, 주어진 2차원 배열에서 탐색을 진행하고, 스택에 차례대로 "push_back" 합니다.

 간단하게 stack(바구니)에 저장된 이전 항목과 현재 저장할 항목을 비교할 수 있지만, STL 알고리즘을 활용해보고자 "adjacent_find"를 사용해보겠습니다!

 

굉장히 간단합니다. 바로 코드를 살펴보겠습니다.

 

* 주의할 점은 "N x N" 격자 밑에 있는 숫자는 "row"의 인덱스이며, "[a][b]" 에서 b를 의미합니다!

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves)
{
    int answer = 0;
    // 뽑은 인형을 담을 벡터
    vector<int> s;

    for (int i = 0; i < moves.size(); i++)
    {
        int index = moves[i] - 1;
        for (int j = 0; j < board.size(); j++)
        {
            if (board[j][index] != 0)
            {
                int ele = board[j][index];

                s.push_back(ele);
                board[j][index] = 0;
                // 2개 이상 있을 경우
                if (s.size() >= 2)
                {
                    // 인접한 중복 두 원소 찾기, 있다면 중복 원소들 중 첫 번째 원소의 반복자 반환
                    auto it = adjacent_find(begin(s), end(s));
                    if (it != end(s))
                    {
                        s.pop_back();
                        s.pop_back();

                        answer += 2;
                    }
                }
                break;
            }
        }
    }

    return answer;
}

 

[Basic C++] #32-2_STL 탐색 알고리즘

"adjacent_find()" 알고리즘의 자세한 내용은 위 링크를 살펴보세요.

 

간단하게, "stack"에 새로운 항목을 저장할 때마다 직전 항목과 "중복"되는 항목인지 체크하고,

중복이라면 해당 항목들을 삭제해줍니다!