[PCCP] Lv1: 크레인 인형 뽑기 게임(64061) 해설

문제

- 문제 링크: 크레인 인형 뽑기 게임

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: board의 행 혹은 열의 길이

- M: moves의 길이

- board를 순회하는 과정은 O(N^2)

- moves를 순회하는 과정은 O(M)

- 총 시간 복잡도: O(N^2 + M)

#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    // 보드 열 크기만큼 스택 생성
    stack<int> lanes[board[0].size()];
    // 보드 가장 밑의 행부터 위로 올라가며 순회
    for (int i = board.size() - 1; i >= 0; --i) {
        for (int j = 0; j < board[0].size(); ++j) {
            // 블럭이 있으면 해당 열을 스택에 푸시
            if (board[i][j]) {
                lanes[j].push(board[i][j]);
            }
        }
    }
    
    // 보드판에서 꺼낸 인형을 담을 bucket, 사라진 인형의 개수를 저장할 answer 선언
    stack<int> bucket;
    int answer = 0;
    
    for (int m : moves) {
        // 해당 lane에 블러이 있으면
        if (lanes[m - 1].size()) {
            int doll = lanes[m - 1].top();
            lanes[m - 1].pop();
            // bucket에 블럭이 있고, 가장 최근에 들어간 블럭과 현재 블럭이 같은지 확인
            if (bucket.size() && bucket.top() == doll) {
                bucket.pop();
                answer += 2;
            } else {
                bucket.push(doll);
            }
        }
    }
    return answer;
}

solution 2)

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> stack;
    
    int tmp = 0;
    for (int i = 0; i < moves.size(); i++)
    {
        tmp = moves[i] - 1;
        for (int j = 0; j < board.size(); j++)
        {
            if (board[j][tmp] != 0)
            {
                if ((stack[stack.size()-1] == board[j][tmp]) && stack.size() > 0)
                {
                    stack.pop_back();
                    answer += 2;
                }
                else
                    stack.push_back(board[j][tmp]);
                board[j][tmp] = 0;
                break;
            }
        }
        // if ((stack.size() > 1) && (stack[stack.size()-2] == stack[stack.size()-1]))
        // {
        //     stack.pop_back();
        //     stack.pop_back();
        //     answer += 2;
        // }
    }
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: board의 행 혹은 열의 길이

- M: moves의 길이

- board를 순회하는 과정은 O(N^2), moves를 순회하는 과정은 O(M)이므로 최종 시간 복잡도는 O(N^2 + M)

- N은 최대 30이고 M은 최대 1,000이므로 O(M) 혹은 O(N^2)으로 생각 가능

- 최악의 경우 연산 횟수: 30^2 + 1,000

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        // 각 열에 대한 스택을 생성
        Stack<Integer>[] lanes = new Stack[board.length];
        for (int i = 0; i < lanes.length; ++i) {
            lanes[i] = new Stack<>();
        }
        
        // board를 역순으로 탐색하여, 각 열의 인형을 lanes에 추가
        for (int i = board.length - 1; i >= 0; --i) {
            for (int j = 0; j < board[i].length; ++j) {
                if (board[i][j] > 0) {
                    lanes[j].push(board[i][j]);
                }
            }
        }
        
        // 인형을 담을 bucket을 생성
        Stack<Integer> bucket = new Stack<>();
        // 사라진 인형의 총 개수를 저장할 변수를 초기화
        int answer = 0;
        
        // moves를 순회하며, 각 열에서 인형을 뽑아 bucket에 추가
        for (int move: moves) {
            if (!lanes[move - 1].isEmpty()) { // 해당 열에 인형이 있는 경우
                int doll = lanes[move - 1].pop();
                // 바구니에 인형이 있고, 가장 위에 있는 인형과 같은 경우
                if (!bucket.isEmpty() && bucket.peek() == doll) {
                    bucket.pop();
                    answer += 2;
                }
                else { // 바구니에 인형이 없거나, 가장 위에 있는 인형과 다른 경우
                    bucket.push(doll);
                }
            }
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: board의 행 혹은 열의 길이

- M: moves의 길이

- board를 순회하는 과정: O(N^2)

- moves를 순회하는 과정: O(M)

- 최종시간복잡도: (N^2 + M)

def solution(board, moves):
    # 각 열에 대한 스택을 생성
    lanes = [[] for _ in range(len(board[0]))]
    
    # board를 역순으로 탐색하며, 각 열의 인형을 lanes에 추가
    for i in range(len(board) - 1, -1, -1):
        for j in range(len(board[0])):
            if board[i][j]:
                lanes[j].append(board[i][j])
                
    # 인형을 담을 bucket을 생성
    bucket = []
    
    # 사라진 인형의 총 개수를 저장할 변수를 초기화
    answer = 0
    
    # moves를 순회하며, 각 열에 인형을 뽑아 bucket에 추가
    for m in moves:
        if lanes[m - 1]: # 해당 열에 인형이 있는 경우
            doll = lanes[m - 1].pop()
        
            if bucket and bucket[-1] == doll: # 바구니에 인형이 있고, 가장 위에 있는 인형과 같은 경우
                bucket.pop()
                answer += 2
            else:
                bucket.append(doll)
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: board의 행 혹은 열의 길이

- M: moves의 길이

- board를 순회하는 과정: O(N^2)

- moves를 순회하는 과정: O(M)

- 최종시간복잡도: (N^2 + M)

function solution(board, moves) {
    // 각 열에 대한 스택을 생성
    const lanes = [...Array(board[0].length)].map(() => []);
    
    // board를 역순으로 탐색하며, 각 열의 인형을 lanes에 추가
    for (let i = board.length - 1; i >= 0; --i) {
        for (let j = 0; j < board[0].length; ++j) {
            if (board[i][j]) {
                lanes[j].push(board[i][j]);
            }
        }
    }
    
    // 인형을 담을 bucket을 생성
    const bucket = [];
    
    // 사라진 인형의 총 개수를 저장할 변수 초기화
    let answer = 0;
    
    // moves를 순회하며, 각 열에서 인형을 뽑아 bucket에 추가
    for (const m of moves) {
        if (lanes[m - 1].length > 0) {
            // 해당 열에 인형이 있는 경우
            const doll = lanes[m - 1].pop();
            
            if (bucket.length > 0 && bucket[bucket.length - 1] === doll) {
                // 바구니에 인형이 있고, 가장 위에 있는 인형과 같은 경우
                bucket.pop();
                answer += 2;
            } else {
                // 바구니에 인형이 없거나, 가장 위에 있는 인형과 다른 경우
                bucket.push(doll);
            }
        }
    }
    
    return answer;
}

solution 2)

import

solution 3)

import