Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Android
- hackerrank
- utility
- 2018 KAKAO BLIND RECRUITMENT
- RAII
- 백트랙
- backtrack5
- setting
- unique_ptr
- 2019 카카오 개발자 겨울 인턴십
- BOJ
- Algorithm
- modern C++
- 안드로이드
Archives
- Today
- Total
K-D²
2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임 본문
문제 링크 : programmers.co.kr/learn/courses/30/lessons/64061
코딩테스트 연습 - 크레인 인형뽑기 게임
[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4
programmers.co.kr
문제 풀이
$N * N$으로 이루어진 2차원 정수 벡터 board와 크레인을 어느 열(column)에서 작동시켰는지를 의미하는 1차원 정수 벡터 moves가 주어진다.
board에는 인형이 들어있는데 인형은 $[1, 100]$ 정수로 표현되고 0인 경우에는 인형이 없는 것이다.
크레인은 인형을 집어서 바구니에 스택 형태로 쌓게 되는데, 바구니에 인형을 넣을 때 동일한 인형이 2개가 되면 해당 인형은 터져서 사라진다.
(또한, 문제에서 바구니는 모든 인형이 들어갈 수 있을 만큼 크다고 가정했으므로 바구니 크기는 고려하지 않아도 된다.)
이처럼 크레인이 모든 이동을 마쳤을 때 바구니에서 터지는 인형이 몇 개인지 반환하면 되는 구현 문제이다.
소스 코드
#include <string>
#include <vector>
#include <stack>
using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
stack<int> basket;
const int N = (int)board.size(); // N*N
for (int c : moves) {
--c; // column idx : [0, N)
for (int r = 0; r < N; ++r) {
if (board[r][c] == 0) continue;
if (!basket.empty()) {
int topElem = basket.top();
if (topElem == board[r][c]) {
basket.pop();
answer += 2;
}
else {
basket.push(board[r][c]);
}
}
else {
basket.push(board[r][c]);
}
board[r][c] = 0;
break;
}
}
return answer;
}
'Algorithm > Programmers' 카테고리의 다른 글
2018 KAKAO BLIND RECRUITMENT - 비밀지도 (0) | 2020.12.23 |
---|
Comments