전형적인 구현 문제
상하좌우를 그대로 구현했는데
다른 사람들 풀이 보니까 rotate 를 구현하고 방향 하나만 구현한 것이 많이 보였다..
이렇게하면 확실히 코드 길이는 줄어 들듯 하다.
내 코드를 보면서 불필요한 부분들이 몇개 발견되었다.
먼저 나의 풀이를 소개한다.
만약 배열의 한줄만 생각한다고 가정하자.
[2,2,0,4,4] 의 배열이 있을 때
오른쪽으로 이동하면 [0,0,0,4,8]
왼쪽으로 이동하면 [4,8,0,0,0]
이렇게 될 것이다. 왼쪽으로 이동할 때 어떻게 풀었는지 보자.
똑같은 크기의 0으로 가득차있는 배열 tmp = [0,0,0,0,0] 를 선언및 초기화한다.
그리고 비어있는 Deque 한개를 선언하고 boolean으로 ok =true를 선언하여 이전에 합쳐졌는지 안 합쳐졌는지 체크한다. true일 경우만 합칠 수 있음.
[2,2,0,4,4] 를 왼쪽에서 부터 살펴본다.
deque가 비어있으면 무조건 넣는다.
1. Deque = [2]
2. ok 가 true 이고 deque의 마지막원소와 같으므로 합칠 수 있다. 그래서 deque 마지막을 꺼낸뒤 합친다. 그리고 ok = false 한다.
Deque = [4]
3. 0 이므로 넘어간다.
Deque = [4]
4. ok 가 false 이므로 deque에 넣는다. ok = true 한다.
Deque = [4,4]
5. ok가 true이며 deque의 마지막 원소와 같으므로 합칠 수 있다. 그래서 deque 마지막을 꺼낸뒤 합친다. 그리고 ok=false 한다.
Deque = [4,8]
deque에 있는 원소를 왼쪽에서 부터 차례로 채워주면 끝이다.
개선해야 할 점이 있는 데
사실 deque 는 필요없다. 한번의 루프로 바로바로 채워 줄 수 있다.
즉 아까의 예를 들어 설명하면
arr = [2,2,0,4,4] 와 result = [0,0,0,0,0] 이 있다고 한다면
왼쪽에서 부터 살펴보고 결과물의 배열이 어떻게 변하는지 관찰해본다.
idx 를 새로 선언하는데 이는 결과물의 배열에 값이 변하는 곳을 인덱싱 한다.
1. result = [2,0,0,0,0] arr[0] 는 처음은 그대로 넣는다. idx = 0
2. result = [4,0,0,0,0] arr[1] 은 result[idx] 와 같으므로 result[idx] *=2 를 하고 idx++;
3. result = [4,0,0,0,0] arr[2] 가 0이므로 넘어간다.
4. result = [4,4,0,0,0] arr[3] 은 result[idx]==0 이므로 그대로 넣는다. idx 유지
5. result = [4,8,0,0,0] arr[4] 은 result[idx]와 같으므로 result[idx]*=2 를 하고 idx++;
이처럼 풀면 훨씬 빠르게 풀수 있다.
개선 전의 코드를 첨부하고 마무리한다..
import java.util.*;
public class Main{
static int n;
static int answer;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[][] board = new int[n][n];
for(int i=0;i<n;i++) {
board[i] = new int[n];
for(int j=0;j<n;j++){
board[i][j]=sc.nextInt();
}
}
dfs(0,board);
System.out.println(answer);
}
public static void dfs(int idx,int[][] board){
if(idx == 5){
answer = Math.max(answer,
Arrays
.stream(board)
.flatMapToInt(Arrays::stream)
.max()
.getAsInt()
);
}
else{
dfs(idx+1,up(board));
dfs(idx+1,down(board));
dfs(idx+1,right(board));
dfs(idx+1,left(board));
}
}
public static int[][] up(int[][] board){
int[][] tmp = new int[n][n];
for(int i=0;i<n;i++) tmp[i] = new int[n];
for(int j=0;j<n;j++){
Deque<Integer> list = new ArrayDeque<>();
boolean ok = true;
for(int i=0;i<n;i++){
if(board[i][j]!=0) {
if (list.size() == 0) list.addLast(board[i][j]);
else {
int last = list.peekLast();
if (last == board[i][j] && ok) {
list.pollLast();
list.addLast(last * 2);
ok = false;
} else {
list.addLast(board[i][j]);
ok = true;
}
}
}
}
int i =0;
while(!list.isEmpty()){
tmp[i++][j]=list.poll();
}
}
return tmp;
}
public static int[][] down(int[][] board){
int[][] tmp = new int[n][n];
for(int i=0;i<n;i++) tmp[i] = new int[n];
for(int j=0;j<n;j++){
Deque<Integer> list = new ArrayDeque<>();
boolean ok = true;
for(int i=n-1;i>=0;i--){
if(board[i][j]!=0) {
if (list.size() == 0) list.addLast(board[i][j]);
else {
int last = list.peekLast();
if (last == board[i][j] && ok) {
list.pollLast();
list.addLast(last * 2);
ok = false;
} else {
list.addLast(board[i][j]);
ok = true;
}
}
}
}
int i =n-1;
while(!list.isEmpty()){
tmp[i--][j]=list.poll();
}
}
return tmp;
}
public static int[][] right(int[][] board){
int[][] tmp = new int[n][n];
for(int i=0;i<n;i++) tmp[i] = new int[n];
for(int i=0;i<n;i++){
Deque<Integer> list = new ArrayDeque<>();
boolean ok = true;
for(int j=n-1;j>=0;j--){
if(board[i][j]!=0) {
if (list.size() == 0) list.addLast(board[i][j]);
else {
int last = list.peekLast();
if (last == board[i][j] && ok) {
list.pollLast();
list.addLast(last * 2);
ok = false;
} else {
list.addLast(board[i][j]);
ok = true;
}
}
}
}
int j =n-1;
while(!list.isEmpty()){
tmp[i][j--]=list.poll();
}
}
return tmp;
}
public static int[][] left(int[][] board){
int[][] tmp = new int[n][n];
for(int i=0;i<n;i++) tmp[i] = new int[n];
for(int i=0;i<n;i++){
Deque<Integer> list = new ArrayDeque<>();
boolean ok = true;
for(int j=0;j<n;j++){
if(board[i][j]!=0) {
if (list.size() == 0) list.addLast(board[i][j]);
else {
int last = list.peekLast();
if (last == board[i][j] && ok) {
list.pollLast();
list.addLast(last * 2);
ok = false;
} else {
list.addLast(board[i][j]);
ok = true;
}
}
}
}
int j =0;
while(!list.isEmpty()){
tmp[i][j++]=list.poll();
}
}
return tmp;
}
}
'algorithm' 카테고리의 다른 글
| [PYTHON] 매칭 점수(kakao 2019 프로그래머스) (0) | 2020.09.10 |
|---|---|
| [JAVA] 소수 찾기 ( 프로그래머스 ) (0) | 2020.09.04 |
| [JAVA] 후보키 (kakao 2019 프로그래머스) (0) | 2020.08.30 |
| [JAVA] 오픈채팅방 (2019 kakao 프로그래머스) (0) | 2020.08.25 |
| [JAVA] 가사검색 (kakao 2020 프로그래머스) (0) | 2020.08.24 |
댓글