프로그래머스_삼각 달팽이(JAVA)

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

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

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• n은 1 이상 1,000 이하입니다.

---

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

---

[문제 풀이]

달팽이 채우기를 진행할 땐 총 3단계로 나눌 수 있다.

1. 위에서부터 아래 행으로 1씩 증가한 값을 채우고

2. 마지막 행부터 전부가 채워지지 않은 행을 찾은 후, 그 행을 1씩 증가시키며 채운 다음

3. 다시 위의 행으로 올라가며 1씩 증가한 값을 채우는 것이다.

 

즉, 삼각형의 각 변이라고 생각하면, 왼쪽 변은 위에서 아래로, 아래 변은 왼쪽에서 오른쪽으로, 오른쪽 변은 아래에서 위로 채워지는 것을 의미한다.

 

이 세가지 과정을 하나의 턴이라고 생각하고 반복문을 작성하였다.

 

[코드 진행]

1. 우선 총 삼각형을 이루는 칸의 개수는 (n * (n+1)) / 2개이다.

따라서 answer 배열의 크기는 (n * (n+1))/2로 선언해준다.

 

2. int 배열을 저장하는 arraylist를 선언한 후, 각 배열의 크기는 1, 2, ... , n까지로 선언한 n개의 배열을 순차적으로 arraylist에 add한다. 이는 행을 의미한다.

 

3-1. 한 턴이 진행할 때마다 1번 과정을 시작할 행 번호는 2씩 증가한다. 그리고 해당 for문에서 i는 n-count와 같아지기 전까지 진행한다. 그 이유는 i가 n-count와 같은 값이 되면 i번째 행은 이미 2번 과정을 수행한 후의 모든 칸에 달팽이 채우기가 진행된 행이기 때문이다. 따라서 해당 for문의 i값의 범위는 i<n-count까지이다. 또한, 행 번호를 의미하는 i는 한 턴마다 2씩 증가하도록 while문 아래에 i+=2;로 선언하여 작성한다.

 

3-2. j는 열 번호를 의미하고 1번 과정 수행 시, j값은 변화가 없다. 2번 과정 수행 시 j는 1씩 증가하고, 해당 열의 채워지지 않은 마지막 칸에 도착하면 2번 과정은 종료된다.

 

3-3. 3번 과정에서는 i값과 j값 모두 변화한다. 행은 하나씩 위로 올라가므로 i값은 1씩 감소할 것이며, 행마다 가지는 칸의 수가 다르기에 채워지지 않은 마지막 칸의 번호 또한 아래 행과 1씩 차이가 나게 된다. 따라서 j값 또한 1씩 감소하게 된다.

 

4. 3가지 과정이 모두 종료되고 나면 한번의 턴이 종료된 것이므로 count를 1 증가시켜준다. 또한 3-1에서 언급한 i+=2;또한 밑에 작성하여 준다.

 

5. 반복문이 종료될 경우는, 모든 칸에 달팽이 채우기가 진행되어 0이 하나도 없을 때이다. 따라서 3번을 수행할 때, 변화가 하나라도 있다면 ischange값을 true로 변경시켜주고, 3번 과정이 끝나고 나면 ischange 값을 검사해 그 값이 false라면 변화가 없다는 것을 의미하므로 while문을 종료한다.

 

6. while문이 종료되고 나면 arraylist의 값을 answer배열에 옮겨준다. 각 행의 원소를 순서대로 answer 배열에 넣어주고 해당 배열을 반환하며 종료한다.

 

[코드]

import java.util.*;
class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        int num = (n * (n+1)) / 2;
        answer = new int[num];
        ArrayList<int[]> triangle = new ArrayList<>();
    
        for(int i=1;i<=n;i++){
            triangle.add(new int[i]);
        }
        
        int i=0;
        int j=0;
        int nn = 1;
        int count=0;
        boolean ischange = false;
        int[] temp ;
        while(true){
            ischange=false;
            
            for(;i<n-count;i++){
                temp = triangle.get(i);
                if(temp[j]==0){
                    temp[j] = nn++;
                    ischange=true;
                }
                else
                    break;
            }
            i--;
            temp = triangle.get(i);
            
           for(j=j+1;j<=i;j++){
                if(temp[j]==0){
                    temp[j] = nn++;
                    ischange=true;
                }
               
            }
            
            j-=(count+1);
            
            for(i=i-1;i>=count;i--){
                temp =triangle.get(i);
                if(temp[j-1]==0){
                    temp[--j] = nn++;
                    ischange=true;
                }
                else break;
            }
            i+=2;
            count+=1;
            
                    
            if(!ischange)  break;
            
        }
        int k=0;
        for(i=0;i<n;i++){
            temp = triangle.get(i);
            for(j=0;j<temp.length;j++){
                answer[k++] = temp[j];
            }
          
                
        }
        return answer;
    }
}