[프로그래머스]삼각달팽이

코딩테스트 연습 - 삼각 달팽이

문제 풀이

규칙을 찾는 문제다. 그림에서sum의 배열을 리턴 하라는 말은 무시하자. 문제에서 요하는 정답이 뭔지 파악하지 못했어서 적었던 말임.

1. row 를 내려간다.
   • 이는 row를 증가시키는 것
   • cr,cc에서 cr만 증가 언제까지?
     • 값이 0이 아니고
     • range 범위내
2. col 을 증가 시킨다.
   • 이는 col만 증가시키는 것
   • cr, cc에서 cc만 증가 언제까지?
     • 값이 0이 아니고
     • range 범위 내
3. row, col 모두 1씩 감소
   • 언제까지?
     • 값이 0이 아니고
     • range 범위 내

최종 종료 조건은? 1,2,3 연산 을 실행하는데 한 칸도 못 움직인 경우라고 생각해서, 각 연산에서, move를 전혀 하지 않은 경우 false를 리턴하도록 하였다.

• N x N matrix 를 두자 ( N은 1000 이니까 괜찮을 듯 )

// 더러운 풀이.. 
class Solution {
    public int[][] board = new int[1001][1001];
    public int gn; // gn == n  
    public int cr = 1, cc = 1; // 좌표
    public int cnt = 1; // 각 칸에 채워 넣을 값
    public int[] solution(int n) {
        int[] answer = {};
        // n == 1 
        if(n==1)return new int[]{1};
        // Otherwise
        gn = n; 
        board[1][1] = cnt++; 
        while(true){
            if(!moveDown())break;
            if(!moveRight())break;
            if(!moveEdge())break;
        }
        answer = makeAns();
        return answer;
    }
		// board로부터 정답 생성
    public int[] makeAns(){
        // 길이는 4+3+2+1 이니 -> n*(n+1)/2 ..... 
        int[] ans = new int[gn*(gn+1)/2];
        int idx = 0; 
        for(int i=1;i<=gn;i++){
            for(int j=1;j<=i;j++){
                ans[idx++] = board[i][j];
            }
        }    
        return ans;
    }
    // 문제점 : cr ++ 로 끝나버림 -> 칸을 복귀시키는게 필요함
    // 아래로 1
    public boolean moveDown(){
        boolean move = false;
        cr++;
        // range
        for(; cr <= gn;cr++){
            // 이미 채워진 칸
            if(board[cr][cc] != 0)break;
    
            board[cr][cc] = cnt++;
            move = true; 
        }
        // 칸 복귀
        cr--;
        return move; 
    }
    
    // 오른쪽으로  2
    public boolean moveRight(){
        boolean move = false; 
        cc++;
        for(;cc<=gn;cc++){
            if(board[cr][cc]!= 0) break;
            
            board[cr][cc] = cnt++;
            move = true;
        }
        // 칸 복귀
        cc--;
        return move;        
    }
    // 대각선 위로  3
    public boolean moveEdge(){
        boolean move = false;
        cr--;cc--;
        for(;cr >= 0 && cc >= 0 ; cr--,cc--){
            if(board[cr][cc] != 0 )break;
            board[cr][cc] = cnt++;
            move = true;
        }
        // 칸 복귀
        cr++;cc++;
        return move; 
    }
}