프로그래머스 LV.2 - 삼각 달팽이

정수 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]

 

---

이 문제에서는 삼각형을 표현해야 한다.

사각형인 2차원 배열을 표로 나타내면 쉽게 해결할 수 있다.

2차원 배열로 표현된 삼각형

문제 조건인 반시계 방향으로 '달팽이 채우기'를 진행하는 것은 2차원 배열에서 반시계 방향인 

"아래 -> 오른쪽 -> 왼쪽 위"로 진행하는 것이다.

이를 이용하면 다음과 같이 문제 풀이 흐름을 작성할 수 있다.

 

문제 풀이 흐름

1. n x n 2차원 배열 선언

2. 숫자를 채울 현재 위치로 (0,0)으로 설정

3. 방향에 따라 이동할 수 없을 때까지 반복하면서 숫자 채우기

 - a. 아래로 이동하면서 숫자 채우기

 - b. 오른쪽으로 이동하면서 숫자 채우기

 - c. 왼쪽 위로 이동하면서 숫자 채우기

4. 채워진 숫자를 차례대로 1차원 배열에 옮겨서 반환

 

코드 작성

1. n x n 2차원 배열 선언

삼각형을 표현할 2차원 배열과 채워 넣을 숫자를 선언한다.

int [][] triangle = new int [n][n];
int v = 1;

triangle 변수는 2차원 배열로 가로n, 세로n의 삼각형을 표현하기 위해 n x n 2차원 배열로 선언했다.

v변수는 채워 넣을 숫자로, 숫자를 triangle 에 기록할 때마다 1씩 증가한다.

 

2. 숫자를 채울 현재 위치로 (0,0) 으로 설정

int x = 0;
int y = 0;

3. 방향에 따라 이동할 수 없을 때까지 반복하면서 숫자 채우기

 숫자를 triangle에 채워 넣어야 한다. 흐름은 아래 -> 오른쪽 -> 왼쪽 위 순서로 숫자를 계속해서 채워넣어야 한다.

while(true) {
      // 아래로 이동
      
      // 오른쪽으로 이동
      
      // 왼쪽 위로 이동
 }

3  - a. 아래로 이동하면서 숫자 채우기

숫자를 채워 넣은 후 아래로 이동할 수 있으면 반복해서 아래로 진행해야 한다.

아래로 진행하는 것은 y값이 증가하는 것이기 때문에 다음과 같이 작성할 수 있다.

while(true){
   triangle[y][x] = v++;
   if(y + 1 == n || triangle[y + 1][x] != 0) break;
   y += 1;
 }

이 반목문에서 빠져나온 것은 더 이상 아래로 진행할 수 없다는 의미이다.

아래로 행할 수 없다면 오른쪽으로 진행해야 하지만, 오른쪽으로도 진행할 수 없는 경우가 있다.

아래로 진행하는 것이 삼각형을 채우는 마지막 진행 방향이라면 여기서 멈추어야한다.

 

위 그림과 같이 로른쪽으로 이동할 수 없는 경우에는 반복문을 탈출하도록 작성해서 오른쪽으로 이동할 수 있을 때만 진행하도록 한다.

while(true){
   triangle[y][x] = v++;
   if(y + 1 == n || triangle[y + 1][x] != 0) break;
   y += 1;
 }

if (x + 1 n || triangle [y][x+1] != 0) break;
x += 1;

 

 3- b. 오른쪽으로 이동하면서 숫자 채우기

 아래 방향의 코드를 작성했다면 두 방향은 어렵지 않다. 같은 원리로 작성하면서 x, y 값만 바꾸어주면 된다.

while(true){
   triangle[y][x] = v++;
   if(x + 1 == n || triangle[y][x + 1] != 0) break;
   x += 1;
 }

if (triangle [y-1][x-1] != 0) break;
x -= 1;
y -= 1;

 

while(true){
   triangle[y][x] = v++;
   if(triangle[y - 1][x-1] != 0) break;
   x += 1;
   y -= 1;
 }

if (y + 1 n || triangle [y+1][x] != 0) break;
y += 1;

4. 채워진 숫자를 차례대로 1차원 배열에 옮겨서 반환

int index = 0;
for (int i = 0, i<n; i ++){
    for(int j = 0; j <= i; j++){
        result[index++] = triangle[i][j];
        }
     }

 

---

https://www.yes24.com/Product/Goods/117372853

취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편 - 예스24