https://programmers.co.kr/learn/courses/30/lessons/64061
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.
https://tech.kakao.com/2020/04/01/2019-internship-test/
인형을 바구니에 쌓는 것을 스택을 이용해서 구현해준다.
터트려져 사라진 인형의 개수를 구하는 것이므로 터질 때마다 정답에 2씩 더 해주면 된다.
처음에 문제를 제대로 안 읽어서 바구니에 남아있는 인형이 정답인 줄 알고 왜 정답이 안 나오지 하고 있었다...
먼저 moves에 있는 인형을 뽑을 위치는 1부터 시작하므로 인덱스로 사용하기 위해서 1을 빼주고 사용한다.
그리고 해당 위치에서 인형이 있는 곳까지 아래로 쭉쭉 내려간다.
문제 조건에 따라 인형을 발견하지 못하면 그냥 다음 뽑을 위치로 넘어가면 되고, 집어 올린 인형과 바구니 위의 가장 위에 있는 인형을 비교해준다.
바구니(스택)의 가장 위에 있는 인형과 현재 뽑은 인형이 같다면 가장 위에 있는 인형을 스택에서 pop 해주고 정답에 2를 더해준다.
같지 않다면 그냥 뽑은 인형을 바구니(스택)에 push 해준다.
스택에 쌓이든 터져서 사라지든 일단 크레인으로 잡혀서 왔으므로 원래 있던 자리는 0으로 만들어서 빈칸으로 만들어주고 다음 위치로 크레인을 작동시키기 위해서 아래칸으로의 탐색은 중단한다.
|
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
|
#include <string>
#include <vector>
#include <stack>
using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
stack<int> stk;
int n = board.size();
for (int num : moves) {
num -= 1;
for (int i = 0; i < n; i++) {
if (board[i][num] == 0) continue;
if (!stk.empty() && stk.top() == board[i][num]) {
stk.pop();
answer += 2;
}
else {
stk.push(board[i][num]);
}
board[i][num] = 0;
break;
}
}
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ ) (0) | 2020.04.09 |
|---|---|
| 2019 카카오 개발자 겨울 인턴십 튜플 ( C++ ) (3) | 2020.04.09 |
| 프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++ (1) | 2020.03.11 |
| 프로그래머스 [2020카카오공채] 블록 이동하기 c++ (2) | 2020.02.14 |
| 프로그래머스 [2020카카오공채] 괄호 변환 c++ (0) | 2019.10.17 |