[2018 KAKAO BLIND RECRUITMENT] ํ๋ ์ฆ4๋ธ๋ก
๋ฌธ์
๋ฌธ์ ์ค๋ช
๋ธ๋ผ์ธ๋ ๊ณต์ฑ๋ฅผ ํต๊ณผํ ์ ์ ์ฌ์ ๋ผ์ด์ธ์ ์ ๊ท ๊ฒ์ ๊ฐ๋ฐ ์ ๋ฌด๋ฅผ ๋งก๊ฒ ๋์๋ค. ์ด๋ฒ์ ์ถ์ํ ๊ฒ์ ์ ๋ชฉ์ โํ๋ ์ฆ4๋ธ๋กโ. ๊ฐ์ ๋ชจ์์ ์นด์นด์คํ๋ ์ฆ ๋ธ๋ก์ด 2ร2 ํํ๋ก 4๊ฐ๊ฐ ๋ถ์ด์์ ๊ฒฝ์ฐ ์ฌ๋ผ์ง๋ฉด์ ์ ์๋ฅผ ์ป๋ ๊ฒ์์ด๋ค.
โ ์์ ์ผ์ด์ค ์ค๋ช
๋ง์ฝ ํ์ด ์์ ๊ฐ์ด ์ฃผ์ด์ง ๊ฒฝ์ฐ, ๋ผ์ด์ธ์ด 2ร2๋ก ๋ฐฐ์น๋ 7๊ฐ ๋ธ๋ก๊ณผ ์ฝ์ด 2ร2๋ก ๋ฐฐ์น๋ 4๊ฐ ๋ธ๋ก์ด ์ง์์ง๋ค. ๊ฐ์ ๋ธ๋ก์ ์ฌ๋ฌ 2ร2์ ํฌํจ๋ ์ ์์ผ๋ฉฐ, ์ง์์ง๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ 2ร2 ๋ชจ์์ด ์ฌ๋ฌ ๊ฐ ์๋ค๋ฉด ํ๊บผ๋ฒ์ ์ง์์ง๋ค.
๋ธ๋ก์ด ์ง์์ง ํ์ ์์ ์๋ ๋ธ๋ก์ด ์๋๋ก ๋จ์ด์ ธ ๋น ๊ณต๊ฐ์ ์ฑ์ฐ๊ฒ ๋๋ค.
๋ง์ฝ ๋น ๊ณต๊ฐ์ ์ฑ์ด ํ์ ๋ค์ 2ร2 ํํ๋ก ๊ฐ์ ๋ชจ์์ ๋ธ๋ก์ด ๋ชจ์ด๋ฉด ๋ค์ ์ง์์ง๊ณ ๋จ์ด์ง๊ณ ๋ฅผ ๋ฐ๋ณตํ๊ฒ ๋๋ค.
์ ๋ ฅ์ผ๋ก ๋ธ๋ก์ ์ฒซ ๋ฐฐ์น๊ฐ ์ฃผ์ด์ก์ ๋, ์ง์์ง๋ ๋ธ๋ก์ ๋ชจ๋ ๋ช ๊ฐ์ธ์ง ํ๋จํ๋ ํ๋ก๊ทธ๋จ์ ์ ์ํ๋ผ.
์ ๋ ฅ ํ์
- ์ ๋ ฅ์ผ๋ก ํ์ ๋์ด m, ํญ n๊ณผ ํ์ ๋ฐฐ์น ์ ๋ณด board๊ฐ ๋ค์ด์จ๋ค.
- 2 <= n, m <= 30
- board๋ ๊ธธ์ด n์ธ ๋ฌธ์์ด m๊ฐ์ ๋ฐฐ์ด๋ก ์ฃผ์ด์ง๋ค. ๋ธ๋ก์ ๋ํ๋ด๋ ๋ฌธ์๋ ๋๋ฌธ์ A์์ Z๊ฐ ์ฌ์ฉ๋๋ค.
์ถ๋ ฅ ํ์
์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ํ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ๋ช ๊ฐ์ ๋ธ๋ก์ด ์ง์์ง์ง ์ถ๋ ฅํ๋ผ.
์ ์ถ๋ ฅ ์
m | n | board |
---|---|---|
4 | 5 | [โCCBDEโ, โAAADEโ, โAAABFโ, โCCBBFโ] |
6 | 6 | [โTTTANTโ, โRRFACCโ, โRRRFCCโ, โTRRRAAโ, โTTMMMFโ, โTMMTTJโ] |
ํ์ด
public class ProgrammersFriends4Block {
// ์์ ์
๋ ฅ
static int m = 4;
static int n = 5;
static String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
// ๊ตฌํ์ ์ํ ํด๋์ค ๋ณ์
static char[][] newBoard = new char[m][n];
static int[] dr = {0, 1, 1}; // ๋, ๋จ, ๋จ๋
static int[] dc = {1, 0, 1};
static int Answer;
public static void main(String[] args) {
// ๋ฌธ์์ด ์
๋ ฅ ๋ฐฐ์ด์ char ํ์
์ 2์ฐจ์ ๋ฐฐ์ด๋ก ๋ณ๊ฒฝ
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
newBoard[i][j] = board[i].charAt(j);
}
}
// ๊ฒ์ ํ๋ ์ด
while (true) {
boolean stop = search(); // ๊ทผ์ ๋ธ๋ก ํ์ธ
if (stop) break; // ๊ทผ์ ํ๋ ๋ธ๋ก๋ค ์ค ์ง์์ง๋ ๊ฒ์ด ์์ผ๋ฉด ๊ฒ์ ์ข
๋ฃ
delete(); // ๊ทผ์ ํ๋ ๋ธ๋ก ์ ๊ฑฐ
replace(); // ์ ๊ฑฐ๋ ๋ธ๋ก ์๋๋ก ์ ๋ ฌ
}
Answer = countZero(); // ์ง์์ง ๋ธ๋ก ๊ฐ์ ์นด์ดํธ
System.out.println(Answer);
}
// ๊ทผ์ ๋ธ๋ก ํ์ธํ๋ ๋ฉ์๋
static boolean search() {
boolean flag = true; // ์ง์ธ ๊ฒ์ด ์๋์ง ํ์ธํ๊ธฐ ์ํจ
for (int r=0; r<m-1; r++) {
for (int c=0; c<n-1; c++) {
char target = newBoard[r][c]; // ์ข์๋จ ๋ธ๋ก์ ๊ธฐ์ค ๋ธ๋ญ์ผ๋ก ์ก๊ณ ํด๋น ๋ธ๋ญ์ ๋, ๋จ, ๋จ๋๋ถ๋ถ ํ์
if (target != '0') { // ์ด๋ฏธ ๊ณต๋ฐฑ์ผ๋ก ์ฑ์ด ๋ถ๋ถ์ ๊ทผ์ ๋ธ๋ก ํ์ธ ์ํจ
int cnt = 0;
for (int i=0; i<3; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (target == newBoard[nr][nc]) cnt++;
}
if (cnt == 3) { // ๊ทผ์ ๋ธ๋ก 4๊ฐ๊ฐ ๋์ผํ ๊ฒฝ์ฐ
flag = false;
newBoard[r][c] = '1'; // ๊ธฐ์ค ๋ธ๋ญ์ ์ง์์ผ ํจ์ ์ฒดํน
}
}
}
}
return flag;
}
// ๊ทผ์ ํ๋ ๋ธ๋ก ์ ๊ฑฐํ๋ ๋ฉ์๋
static void delete() {
for (int r=0; r<m-1; r++) {
for (int c=0; c<n-1; c++) {
if (newBoard[r][c] == '1') { // search() ๋ฉ์๋ ์คํ ๊ฒฐ๊ณผ ์ฒดํน๋ ๋ธ๋ญ์ ๊ธฐ์ค์ผ๋ก
newBoard[r][c] = '0'; // ํด๋น ๊ธฐ์ค ๋ธ๋ญ ์ง์ฐ๊ธฐ
for (int i=0; i<3; i++) { // ๋, ๋จ, ๋จ๋ ๋ธ๋ญ ์ง์ฐ๊ธฐ
int nr = r + dr[i];
int nc = c + dc[i];
if (newBoard[nr][nc] != '1') newBoard[nr][nc] = '0';
}
}
}
}
}
// ์ ๊ฑฐ๋ ๋ธ๋ญ์ ์๋๋ก ์ ๋ ฌํ๋ ๋ฉ์๋
static void replace() {
for (int c=0; c<n; c++) {
String oneCol = new String();
for (int r=m-1; r>=0; r--) { // ์ด์ ๊ธฐ์ค์ผ๋ก ๊ฐ์ฅ ๋ฐ๋ฅ๋ถํฐ ํ์ธํ์ฌ
if (newBoard[r][c] != '0') { // ๊ณต๋ฐฑ์ด ์๋ ๋ฌธ์๊ฐ ์๊ฒจ์ง ๋ธ๋ญ์ด๋ฉด ๊ธฐ์ต
oneCol += Character.toString(newBoard[r][c]);
}
}
int bottomR = m;
for (int i=0; i<oneCol.length(); i++) { // ์ด์ ๊ธฐ์ค์ผ๋ก ๋ฐ๋ฅ๋ถํฐ ๋ฌธ์๋ฅผ ์ฑ์๋๊ฐ
newBoard[--bottomR][c] = oneCol.charAt(i);
}
if (--bottomR > 0) { // ์ด์ ๊ธฐ์ค์ผ๋ก ๋ฌธ์๊ฐ ์ฑ์์ง์ง ์์ ๋ธ๋ญ๋ค์ ๋ค์ ๊ณต๋ฐฑ์ผ๋ก ์ฑ์
for (int i=bottomR; i>=0; i--) {
newBoard[i][c] = '0';
}
}
}
}
// ์ ๋ต ์ถ๋ ฅ์ ์ํด ๊ณต๋ฐฑ ๋ธ๋ญ ๊ฐ์ ์ธ๋ ๋ฉ์๋
static int countZero() {
int cnt = 0;
for (int r=0; r<m; r++) {
for (int c=0; c<n; c++) {
if (newBoard[r][c] == '0') cnt++;
}
}
return cnt;
}
}
๐ก
- ์๋ฐ๋ก 2์ฐจ์ ๋ฐฐ์ด ๋ค๋ฃจ๋ ์ฐ์ต์ด ํ์ํด์ ์ฌ๊ธฐ์ ๊ธฐ ์ฐพ๋ค๊ฐ ๋ฐ๊ฒฌํ ๋ฌธ์
- 2์ฐจ์ ๋ฐฐ์ด์ ์ ์ด๋ฅด๊ณ ๋ฌ๋๋ ๊ตฌํ ๋ฌธ์
- ํจ์จ์ฑ ์ ์๊ฐ ์๋ค์ด๊ฐ๋ ๋ฌธ์ ๋ผ ๋์ด๊ฐ์ง๋ง, ๋ง์ฝ ํจ์จ์ฑ๋ ์ฑ์ ํ๋ค๋ฉด ๊ฑธ๋ฆด ๋ถ๋ถ์ด ์์ฃผ ๋ง์๋ณด์ด๋ ํ์ด,,,