12100번) 2048 (Easy)

문제 출처 : https://www.acmicpc.net/problem/12100

이번 문제는 테스트케이스가 적어서,

문제 발견하기가 굉장히 어려웠어요.

포기하려는 순간에 

<그림 12>를 1회만 테스트로 돌리니, 해당 문제를 발견할 수 있었어요.

문제를 해결하기 전에 어느정도까지 생각했냐면

비동기인 LinkedList로 구현을 해서 틀리는건가? 까지 생각했어요. 

그래서 해당 코드는 어레이리스트로 구현했네요.

문제가 무엇이었냐면 moveBlock에서

맵의 값을 queue에 삽입할때

0의 값도 추가해서 제대로 된 덧셈 연산이 수행되지 못했습니다.

따라서 0이 아닌 값만 추가하여 해당 문제를 해결했어요.

2018년 4월 8일 - 다듬지 않은 시험 코드 (소요시간 1시간 50분) import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; import java.util.Vector; public class Q12100 { static int mapSize; static long result = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); mapSize = sc.nextInt(); long[][] map = new long[mapSize][mapSize]; for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { map[i][j] = sc.nextInt(); } } for (int i = 0 ; i < 4; i++) { moveBlock(i, 1, map); } System.out.println(result); } static void moveBlock(int where, int count, long[][] map) { long[][] tempMap = new long[mapSize][mapSize]; switch (where) { //상 case 0 : for (int i = 0; i < mapSize; i++) { ArrayList<Long> queue = new ArrayList<>(); for (int j = 0; j < mapSize; j++) { long temp = map[j][i]; if (temp != 0) { queue.add(temp); } } int nowPosition = 0; while(queue.size() > 0) { long tempValue = queue.get(0); queue.remove(0); if (tempValue > 0) { if (queue.size() > 0) { if (tempValue == queue.get(0)) { tempValue *= 2; queue.remove(0); } } tempMap[nowPosition][i] = tempValue; nowPosition += 1; } } } // // for (int i = 0 ; i < mapSize; i++) { // for (int j = 0; j < mapSize; j++) { // System.out.print(map[i][j] + " "); // } // System.out.println(); // } // System.out.println(); break; //하 case 1 : for (int i = 0; i < mapSize; i++) { ArrayList<Long> queue = new ArrayList<>(); for (int j = mapSize-1; j >= 0; j--) { long temp = map[j][i]; if (temp != 0) { queue.add(temp); } } int nowPosition = mapSize-1; while(queue.size() > 0) { long tempValue = queue.get(0); queue.remove(0); if (tempValue > 0) { if (queue.size() > 0) { if (tempValue == queue.get(0)) { tempValue *= 2; queue.remove(0); } } tempMap[nowPosition][i] = tempValue; nowPosition -= 1; } } } // for (int i = 0 ; i < mapSize; i++) { // for (int j = 0; j < mapSize; j++) { // System.out.print(map[i][j] + " "); // } // System.out.println(); // } // System.out.println(); break; //좌 case 2 : for (int i = 0; i < mapSize; i++) { ArrayList<Long> queue = new ArrayList<>(); for (int j = 0; j < mapSize; j++) { long temp = map[i][j]; if (temp != 0) { queue.add(temp); } } int nowPosition = 0; while(queue.size() > 0) { long tempValue = queue.get(0); queue.remove(0); if (tempValue > 0) { if (queue.size() > 0) { if (tempValue == queue.get(0)) { tempValue *= 2; queue.remove(0); } } tempMap[i][nowPosition] = tempValue; nowPosition += 1; } } } // for (int i = 0 ; i < mapSize; i++) { // for (int j = 0; j < mapSize; j++) { // System.out.printf("%2d ", map[i][j]); // } // System.out.println(); // } // System.out.println(); break; //우 case 3 : for (int i = 0; i < mapSize; i++) { ArrayList<Long> queue = new ArrayList<>(); for (int j = mapSize-1; j >= 0; j--) { long temp = map[i][j]; if (temp != 0) { queue.add(temp); } } int nowPosition = mapSize-1; while(queue.size() > 0) { long tempValue = queue.get(0); queue.remove(0); if (tempValue > 0) { if (queue.size() > 0) { if (tempValue == queue.get(0)) { tempValue *= 2; queue.remove(0); } } tempMap[i][nowPosition] = tempValue; nowPosition -= 1; } } } // for (int i = 0 ; i < mapSize; i++) { // for (int j = 0; j < mapSize; j++) { // System.out.print(map[i][j] + " "); // } // System.out.println(); // } // System.out.println(); break; default : break; } if (count == 5) { for (int i = 0 ; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { long max = tempMap[i][j]; if (result < max) { result = max; } } } // if (count == 1) { // System.out.println(where); // for (int i = 0 ; i < mapSize; i++) { // for (int j = 0; j < mapSize; j++) { // System.out.printf("%2d ", tempMap[i][j]); // } // System.out.println(); // } // System.out.println(); return; } else { for (int i = 0 ; i < 4; i++) { moveBlock(i, count+1, tempMap); } } } }

2018년 4월 8일 - 다듬은 코드는 아니고 대충 정리한 코드 import java.util.LinkedList; import java.util.Scanner; public class Q12100 { static int mapSize; static long result = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); mapSize = sc.nextInt(); long[][] map = new long[mapSize][mapSize]; for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { map[i][j] = sc.nextInt(); } } for (int i = 0 ; i < 4; i++) { moveBlock(i, 1, map); } System.out.println(result); } static void moveBlock(int where, int count, long[][] map) { long[][] tempMap = new long[mapSize][mapSize]; switch (where) { //상 case 0 : for (int i = 0; i < mapSize; i++) { LinkedList<Long> queue = new LinkedList<>(); for (int j = 0; j < mapSize; j++) { long temp = map[j][i]; if (temp > 0) { queue.add(temp); } } int nowPosition = 0; while(queue.size() > 0) { long tempValue = queue.pollFirst(); if (queue.size() > 0) { if (tempValue == queue.getFirst()) { tempValue *= 2; queue.removeFirst(); } } tempMap[nowPosition][i] = tempValue; nowPosition += 1; } } break; //하 case 1 : for (int i = 0; i < mapSize; i++) { LinkedList<Long> queue = new LinkedList<>(); for (int j = mapSize-1; j >= 0; j--) { long temp = map[j][i]; if (temp > 0) { queue.add(temp); } } int nowPosition = mapSize-1; while(queue.size() > 0) { long tempValue = queue.pollFirst(); if (queue.size() > 0) { if (tempValue == queue.getFirst()) { tempValue *= 2; queue.removeFirst(); } } tempMap[nowPosition][i] = tempValue; nowPosition -= 1; } } break; //좌 case 2 : for (int i = 0; i < mapSize; i++) { LinkedList<Long> queue = new LinkedList<>(); for (int j = 0; j < mapSize; j++) { long temp = map[i][j]; if (temp > 0) { queue.add(temp); } } int nowPosition = 0; while(queue.size() > 0) { long tempValue = queue.pollFirst(); if (queue.size() > 0) { if (tempValue == queue.getFirst()) { tempValue *= 2; queue.removeFirst(); } } tempMap[i][nowPosition] = tempValue; nowPosition += 1; } } break; //우 case 3 : for (int i = 0; i < mapSize; i++) { LinkedList<Long> queue = new LinkedList<>(); for (int j = mapSize-1; j >= 0; j--) { long temp = map[i][j]; if (temp != 0) { queue.add(temp); } } int nowPosition = mapSize-1; while(queue.size() > 0) { long tempValue = queue.pollFirst(); if (queue.size() > 0) { if (tempValue == queue.getFirst()) { tempValue *= 2; queue.removeFirst(); } } tempMap[i][nowPosition] = tempValue; nowPosition -= 1; } } break; default : break; } if (count == 5) { for (int i = 0 ; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { long max = tempMap[i][j]; if (result < max) { result = max; } } } return; } else { for (int i = 0 ; i < 4; i++) { moveBlock(i, count+1, tempMap); } } } }