프로그래머스_삼각 달팽이_Day21

오늘은 알고리즘 챌린지 21일 차이다. level2에 분류된 구현 문제를 가져와봤다. 

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

최대한 단순하게 풀어보려 했지만, 규칙은 찾기가 어려웠고,,, 구현을 하고자 한다면 n의 크기가 1000으로 크지 않기 때문에 조건만 잘 설정해 주면 된다. 

이런 문제는 실제로 삼각 형태의 자료구조를 만들 수 없기 때문에, 구현 가능한 2차원 배열 상태에서 논리적으로 삼각 배열을 구현하는 것이다. 배열에 코드를 채우는 순서는 일정하다. 아래로 이동하다가, 이미 채워졌거나 배열의 범위를 벗어나면 오른쪽으로 이동, 오른쪽으로 이동하다가 이미 채워졌거나 배열의 범위를 벗어나면 좌상단 대각선으로 이동, 대각선 이동하다가 이미 채워져 있으면 다시 아래로 이동하는 구조로 무한 반복하는 것이다. 

n의 크기가 주어지면, 가장 마지막에 채워질 수(target)는 n*(n+1) / 2로 구할 수 있기 때문에, cnt를 1부터 증가 시키다가  cnt가 target과 동일해지는 경우 마지막으로 배열에 값을 채우고 반복문을 탈출하면 된다. 

import java.util.*;
import java.util.stream.*;
class Solution {
    int [][]map = new int[1000][1000];
    //이동 방향은 반드시 하나만 true로 설정되어 있어야 한다.
    boolean down = true; 
    boolean right = false; 
    boolean upCross = false; 
    
    public int[] solution(int n) {
        
        int x = 0; 
        int y = 0;
        int target = (n * (n+1)) / 2;
        
        int cnt = 0;
        while(down || right || upCross) { //사실상 true로 잡아도 된다. 
            cnt++;
            map[x][y] = cnt;
            if(cnt == target) break;
            //진행방향이 아래였다면, 
            if(down) {
                //다음 위치가 이미 채워졌거나 배열의 범위를 벗어나지 않았는지 체크
                if(x+1 >= n || map[x+1][y] != 0) {
                    down = false;
                    right = true;
                    y++;
                }else {//아니라면 계속 진행
                    x++;
                }
            }else if (right){
                if(y+1 >= n || map[x][y+1] != 0){
                    right = false;
                    upCross = true;
                    x--;
                    y--;
                }else {
                    y++;
                }
            }else if(upCross) {
                if(map[x-1][y-1] != 0) {
                    upCross = false;
                    down = true;
                    x++;
                }else{
                    x--;
                    y--;
                }

            }

        }
        //값이 채워진 원소만 리스트에 담은 후 반환
        List<Integer> answer = new ArrayList<>();
        for(int i=0; i<n; i++){
            for (int j=0; j<n; j++) {
                if(map[i][j] == 0) continue;
                answer.add(map[i][j]);
            }
        }
        int[] result = answer.stream().mapToInt(Integer::intValue).toArray();
        return result;
    }
}