문제 링크:
카카오 신입 공채 1차 코딩 테스트 문제 해설
‘블라인드’ 전형으로 실시되어 시작부터 엄청난 화제를 몰고 온 카카오 개발 신입 공채. 그 첫 번째 관문인 1차 코딩 테스트가 지난 9월 16일(토) 오후 2시부터 7시까지 장장 5시간 동안 온라인으로 치러졌습니다. 지원자들의 개발 능력을 잘 검증하기 위해 출제 위원들이 한 땀 한 땀 독창적이고 다양한 문제들을 만들어 냈고 문제에 이상은 없는지, 테스트케이스는 정확한지 풀어보고 또 풀어보며 […]
tech.kakao.com
입출력:
| TC# | 입력 | 출력 |
| 1 | 4 5 CCBDE AAADE AAABF CCBBF |
14 |
| 2 | 6 6 TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ |
15 |
코드:
// 1시간 14분 소요
/* 1. 아래에서 위로 올라가는 거니까 --r, r >= 0 */
/* 2. eq 같기만 한다고 되는 게 아니라 t로 같아야 한다는 조건 필요! */
/* 3. 블록 제거하고 board에도 변경사항 반영해야 */
/* 4. 제거는 한 번만 되도록 제거 후 rmv에서 해당 부분 초기화해주기*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int m, n;
vector<string> board;
int eq[30][30], rmv[30][30];
int ans;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> m >> n;
for (int i = 0; i < m; ++i) {
string str;
cin >> str;
board.push_back(str);
}
for (int t = 1;; ++t) {
// 좌우 동일면 eq에 표시
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n - 1; ++c) {
if (board[r][c] != '0' && board[r][c] == board[r][c + 1]) {
eq[r][c] = t;
}
}
}
// 좌우상하 동일하면 rmv에 표시
for (int r = 0; r < m - 1; ++r) {
for (int c = 0; c < n - 1; ++c) {
if (eq[r][c] == t && eq[r + 1][c] == t && board[r][c] == board[r + 1][c]) {
rmv[r][c] = rmv[r][c + 1] = rmv[r + 1][c] = rmv[r + 1][c + 1] = t;
}
}
}
// 각 열별로 당기기
int rmvd = 0;
for (int c = 0; c < n; ++c) {
for (int r = m - 1; r >= 0 && board[r][c] != '0';) { /* 1 */
for (; r >= 0 && board[r][c] != '0' && rmv[r][c] != t; --r); // 제거 대상 블록 찾기
if (r == -1 || board[r][c] == '0') // 없으면 pass
break;
int nr, gap = 0;
for (nr = r; rmv[nr][c] == t; --nr) { // 제거 대상 블록이 있으면
rmv[nr][c] = 0;
++gap;
}
/* 1 */
for (; nr >= 0 && board[r][c] != '0'; --nr) { // 보드의 끝이나 쌓인 블록의 끝에 다다를 때까지 제거 대상 블록 만킁 블록 내리기
board[nr + gap][c] = board[nr][c];
}
for (nr = nr + gap; nr >= 0 && board[r][c] != '0' != -1; --nr) {
board[nr][c] = '0'; /* 3 */
}
rmvd += gap;
}
}
if (rmvd == 0)
break;
ans += rmvd;
}
cout << ans;
return 0;
}