카카오 블라인드 채용 신입 공채 1차 코딩 테스트) 6번 문제

문제 출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

지난 9월 16일(토) 오후 2시부터 오후 7시까지 5시간동안 진행한 코딩테스트입니다.

보통 코딩 테스트 문제 유출하면 안되는데, 카카오는 문제를 공개하고 직접 문제 해설도 진행했습니다.

시험 당시 제출했던 코드와 해설을 참고하여 수정한 코드를 올리겠습니다.

이것 또한 공부가 되겠죠.

함정은 없습니다.

7문제를 5시간안에 풀수 있게끔 6번 문제에 여러조건을 제시하여 문제의 난이도를 낮췄네요.

public class kakao6 { static boolean isBoom; static int boomNum, boardM, boardN; static int[][] intBoard; public static void main(String[] args) { solution(4, 5, new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"}); solution(6, 6, new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"}); } static int solution(int m, int n, String[] board) { boardM = m; boardN = n; intBoard = new int[boardM][boardN]; boomNum = 0; for(int i=0; i<m; i++) { for(int j=0;j<n;j++) { intBoard[i][j] = Integer.valueOf(board[i].charAt(j)); } } do { setBoom(); removeBoom(); downBlock(); //showBoard(m, n); } while(isBoom); System.out.println(boomNum); return boomNum; } static void setBoom() { isBoom = false; for(int i=0; i<boardM-1; i++) { for(int j=0;j<boardN-1;j++) { int temp = intBoard[i][j] % 100; if (temp != -1 && temp == intBoard[i][j+1] % 100 && temp == intBoard[i+1][j] % 100 && temp == intBoard[i+1][j+1] % 100) { checkBoom(i,j); } } } } static void checkBoom(int y, int x) { isBoom = true; for (int i = y; i <= y+1; i++) { for (int j = x; j <= x + 1; j++) { if (intBoard[i][j] < 100) { intBoard[i][j] += 100; boomNum ++; } } } } static void removeBoom() { for(int i=0; i<boardM; i++) { for(int j=0;j<boardN;j++) { if (intBoard[i][j] > 100) { //100이상이면 무조건 터지는 놈들 intBoard[i][j] = 0; } } } } static void downBlock() { for(int j=0;j<boardN;j++){ for(int i=boardM-1; i>=0; i--) { //밑에서부터 탐색한다. if (intBoard[i][j] == 0) { //터진 놈이면 int k; for (k=i; k>0; k--) { intBoard[k][j] = intBoard[k-1][j]; } intBoard[0][j] = -1; i +=1; //0 값이 내려올수 있기 때문에 다시 한번더 수행  } } } } static void showBoard() { for(int i=0; i<boardM; i++) { for(int j=0;j<boardN;j++) { System.out.printf("%4d", intBoard[i][j]); } System.out.print("\n"); } System.out.print("\n"); } }

이중포문을 많이 사용했습니다.

시간이 나면 더 좋은 알고리즘으로 계산해봐야겠습니다.

- 추가 코드 (17년 10월 25일) -

public class Q6 { public static void main(String[] args) { solution(4, 5, new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"}); solution(6, 6, new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"}); } static int[][] newBoard; static int x, y; static int result = 0; static void solution(int m, int n, String[] board) { y = m; x = n; setNewBoard(board); boolean isRe = true; while ( isRe ) { searchBlock(); isRe = boomBlock(); downBlock(); } System.out.println(result); } static void setNewBoard(String[] board) { result = 0; newBoard = new int[y][x]; for ( int i = 0; i < y; i++ ) { String tempString = board[i]; for ( int j = 0; j < x; j++ ) { newBoard[i][j] = tempString.charAt(j); } } } static void searchBlock() { for ( int i = 0; i < y-1; i++ ) { for ( int j = 0; j < x-1; j++ ) { int temp = (newBoard[i][j]) % 100; if ( temp > 0 && newBoard[i][j+1] % 100 == temp && newBoard[i+1][j] % 100 == temp && newBoard[i+1][j+1] % 100 == temp ) { newBoard[i][j] = temp + 100; newBoard[i][j+1] = temp + 100; newBoard[i+1][j] = temp + 100; newBoard[i+1][j+1] = temp + 100; } } } } static boolean boomBlock() { boolean boom = false; for ( int i = 0; i < y; i++ ) { for ( int j = 0; j < x; j++ ) { if ( newBoard[i][j] >= 100 ) { newBoard[i][j] = 0; boom = true; result += 1; } } } return boom; } static void downBlock() { for ( int i = 0; i < x; i++ ) { for ( int j = y-1; j >= 0; j-- ) { if ( newBoard[j][i] == 0 ) { for ( int k = j; k > 0; k-- ) { newBoard[k][i] = newBoard[k-1][i];  } newBoard[0][i] = -1; j+=1; } } } } }

지난 코드를 다시 정리했습니다.

2018년 1월 29일 public class kakao6 { static boolean doNext; public static void main(String[] args) { solution(4, 5, new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"}); solution(6, 6, new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"}); } static void solution(int m, int n, String[] stringBlocks) { doNext = true; //int배열로 바꾸기 int[][] intBlocks = getIntBlocks(m, n, stringBlocks); while (doNext) { //제거 할 블록 찾기 intBlocks = getSearchBoomBlocks(m, n, intBlocks); //블록 제거하기 intBlocks = getAfterBoomBlocks(m, n, intBlocks); //블록 내리기 intBlocks = getAfterMoveBlocks(m, n, intBlocks); } printResult(m, n, intBlocks); } static int[][] getIntBlocks(int m, int n, String[] stringBlocks) { int[][] intBlocks = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { intBlocks[i][j] = stringBlocks[i].charAt(j); } } return intBlocks; } static int[][] getSearchBoomBlocks(int m, int n, int[][] intBlocks) { doNext = false; for (int i = 0; i < m-1; i++) { for (int j = 0; j < n-1; j++) { int tempBlock = intBlocks[i][j] % 100; if (tempBlock == 0) { continue; } boolean isBoom = intBlocks[i+1][j] % 100 == tempBlock && intBlocks[i][j+1] % 100 == tempBlock && intBlocks[i+1][j+1] % 100 == tempBlock; if (isBoom) { intBlocks[i][j] += 100; intBlocks[i+1][j] += 100; intBlocks[i][j+1] += 100; intBlocks[i+1][j+1] += 100; doNext = true; } } } return intBlocks; } static int[][] getAfterBoomBlocks(int m, int n, int[][] intBlocks) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { boolean isBoomBlock = intBlocks[i][j] >= 100; if (isBoomBlock) { intBlocks[i][j] = -1; } } } return intBlocks; } static int[][] getAfterMoveBlocks(int m, int n, int[][] intBlocks) { for (int i = 0; i < n; i++) { for (int j = m-1; j > 0; j--) { boolean isBoomedBlock = intBlocks[j][i] == -1; if (isBoomedBlock) { for (int k = j; k > 0; k--) { intBlocks[k][i] = intBlocks[k-1][i]; } intBlocks[0][i] = 0; j += 1; } } boolean isBoomedBlock = intBlocks[0][i] == -1; if (isBoomedBlock) { intBlocks[0][i] = 0; } } return intBlocks; } static void printResult(int m, int n, int[][] intBlocks) { int numRemovedBlock = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { boolean isRemovedBlock = intBlocks[i][j] == 0; if (isRemovedBlock) { numRemovedBlock += 1; } System.out.printf("%2c",intBlocks[i][j]); } System.out.println(); } System.out.println("Result = " + numRemovedBlock + "\n"); } }

좀 더 좋은 코드 및 다듬을 부분을 알려주시면 감사히 학습하겠습니다.