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

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

프로그래머스

 
 
삼각형을 달팽이처럼 뱅글뱅글 채우는 문제. 처음엔 방향마다 while문을 따로 두는 방식으로 풀었고, 이후에 방향 벡터(dx/dy)로 while문 하나에 몰아넣는 방식으로 다시 풀어봤다. 두 풀이를 나란히 정리하면서, 각각에서 내가 헷갈렸던 부분까지 함께 남긴다.

문제 요약

 

• 정수 n이 주어지면, n줄짜리 삼각형을 만든다.
• 1부터 시작하는 숫자를 바깥에서 안쪽으로 달팽이처럼 채운다.
• 채운 결과를 1차원 배열로 반환한다.

예를 들어 n = 4면 삼각형은 이렇게 채워진다.

i=0 :  1
i=1 :  2   9
i=2 :  3   10  8
i=3 :  4   5   6   7

최종 반환값은 이걸 위에서부터 왼→오로 읽은 1차원 배열이다.

[1, 2, 9, 3, 10, 8, 4, 5, 6, 7]

두 풀이 모두 아래 → 오른쪽 → 대각선 위 세 방향을 반복하며 채운다는 큰 그림은 같다. 방향 전환을 "어떻게 표현하느냐"만 다르다.
 

풀이 1. while문 3개 방식

 

아이디어

세 방향을 각각 별도의 while문으로 처리한다. 바깥 while(true)로 전체를 감싸서, 삼각형이 다 채워질 때까지 세 방향을 계속 순환한다.

1. 아래로 이동하며 채우기 (막히면 방향 전환)
2. 오른쪽으로 이동하며 채우기 (막히면 방향 전환)
3. 대각선 위(왼쪽 위)로 이동하며 채우기 (막히면 방향 전환)

각 방향마다 구조가 완전히 똑같다.

• 안쪽 while → 그 방향으로 막힐 때까지 채운다.
• while 직후의 if(...) break; → 다음 방향으로 꺾기 전 "더 갈 곳이 있는지" 확인. 없으면 전체 종료.
• 좌표 이동 → 갈 곳이 있으면 다음 방향으로 한 칸 옮겨두고 다음 while로 진입.

 

헷갈렸던 포인트

 

① triangle[y+1][x] != 0이 뭘 확인하는 거지?

 
"다음 내려갈 칸에 이미 숫자가 채워져 있는지" 확인하는 조건이다. 핵심은 자바에서 배열은 생성하면 0으로 초기화된다는 점.

int[][] triangle = new int[n][n];  // 모든 칸이 0으로 시작

자료형 기본값

int, long 등 정수형	0
double, float	0.0
boolean	false
참조 타입(String, 객체)	null

그래서 0은 "아직 안 채운 빈 칸" 이라는 뜻으로 쓰인다.

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

• y + 1 == n : 바닥(경계)에 도달했는가? → 더 내려가면 배열 범위를 벗어남
• triangle[y + 1][x] != 0 : 다음 칸이 이미 차 있는가? → 이전 바퀴의 흔적을 덮어쓰면 안 됨

즉 벽을 만났거나, 이미 채운 칸을 만나면 멈춰라 는 의미다.

 

② while문 끝난 직후의 if break; + 좌표 이동은 왜 붙지?

아래 이동 while이 끝난 직후 이 두 줄을 보자.

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

while을 빠져나온 순간, 현재 위치는 아래로 갈 수 있는 마지막 칸에 멈춰 있다. 이제 방향을 오른쪽으로 틀어야 하는데, 그 전에 두 가지를 처리한다.
① if(...) break; —  진짜 끝인지 확인 (전체 종료용) 오른쪽으로 꺾으려는데 오른쪽마저 막혀 있다면? → 삼각형을 다 채웠다는 뜻이다. x+1==n(벽)이거나 triangle[y][x+1]!=0(이미 참)이면 바깥 while 전체를 종료한다.
 
② x += 1; — 다음 방향으로 출발점 옮기기 아직 갈 곳이 있으면, 오른쪽으로 한 칸 미리 옮겨두고 다음(오른쪽 이동) while로 넘어간다.
이 패턴이 세 방향 모두 똑같이 반복된다.

• 아래 while 끝 → 오른쪽 확인 후 x += 1
• 오른쪽 while 끝 → 대각선 위 확인 후 x -= 1; y -= 1;
• 대각선 위 while 끝 → 아래 확인 후 y += 1

한 문장 요약: while 직후 코드는 다음 방향으로 꺾기 전, 갈 곳이 없으면 전체를 끝내고, 있으면 다음 방향으로 한 칸 옮겨 출발한다는 방향 전환 스위치다.

 

전체 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int n) {
        int[][] triangle = new int[n][n];
        int v = 1;
        int y = 0, x = 0;

        while (true) {
            // 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;

            // 2. 오른쪽으로 이동
            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;

            // 3. 대각선 위로 이동
            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;
        }

        // 2차원 → 1차원 변환
        int[] result = new int[v - 1];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {  // i행에는 i+1개의 숫자
                result[index++] = triangle[i][j];
            }
        }
        return result;
    }
}

 
 
 

풀이 2. 방향 벡터(dx/dy) 방식

아이디어

세 방향을 while문으로 나누는 대신, "방향"을 데이터로 다룬다.

private static final int[] dx = {0, 1, -1};
private static final int[] dy = {1, 0, -1};  // 아래 → 오른쪽 → 왼쪽 위

 
d dx[d] dy[d] 의미

d	dx[d]	dy[d]	의미
0	0	+1	아래로 (y 증가 = 행이 아래로)
1	+1	0	오른쪽으로 (x 증가)
2	-1	-1	왼쪽 위 대각선 (x, y 둘 다 감소)

d 값 하나만 바꾸면 이동 방향이 통째로 바뀐다. while문 3개로 나누던 걸, 여기선 d로 방향만 갈아끼우면서 while 하나로 처리한다.

 

while문 한 줄씩

while(true){
    triangle[y][x] = v++;        // ① 현재 칸 채우기
    int nx = x + dx[d];          // ② 다음 칸 "후보" 계산
    int ny = y + dy[d];
    if(nx==n || ny==n || nx==-1 || ny==-1 || triangle[ny][nx]!=0){  // ③ 후보가 막혔나?
        d = (d+1)%3;             // ④ 방향 틀기
        nx = x + dx[d];          // ⑤ 새 방향으로 후보 다시 계산
        ny = y + dy[d];
        if(nx==n || ny==n || nx==-1 || ny==-1 || triangle[ny][nx]!=0) break;  // ⑥ 그것도 막혔으면 끝
    }
    x = nx;                      // ⑦ 검사 통과 → 실제 이동
    y = ny;
}

 
① 현재 칸 채우기 — 지금 위치에 숫자를 넣고 v를 1 올린다.
② 다음 칸 후보계산 — nx, ny는 지금 방향으로 한 칸 갔을 때의 위치. 아직 이동한 게 아니라 후보만 계산한 것이다.
③ 후보가 막혔는지 검사

• nx==n || ny==n : 오른쪽/아래 벽을 벗어남
• nx==-1 || ny==-1 : 왼쪽/위 벽을 벗어남
• triangle[ny][nx]!=0 : 이미 채워진 칸

④ 방향 바꾸기 — d = (d+1)%3. % 3이 방향을 0→1→2→0… 로 순환시킨다. 2 다음에 (2+1)%3=0으로 다시 아래로 돌아가는 게 달팽이가 계속 도는 원리다.
⑤ 새 방향으로 후보 다시 계산
⑥ 방향 틀었는데도 막혔으면 → 전체 종료 — 방향을 한 번 틀었는데 새 방향마저 막혀 있으면, 어느 방향으로도 갈 곳이 없다는 뜻 = 삼각형 다 채움 → break.

검사가 두 번 들어가는 이유: ③ 지금 방향 막힘? → 막히면 방향만 틀어보자 / ⑥ 틀어본 방향도 막힘? → 그것도 막히면 완전히 끝.

⑦ 실제로 이동 — 검사를 다 통과했으면 그제서야 x, y를 옮긴다.

 

 

헷갈렸던 포인트: 왜 x = nx; y = ny;를 마지막에 하지?

 
"미리 계산만 해두고, 안전이 확인되면 그때 실제로 옮긴다" 는 구조 때문이다.

• x, y : 지금 실제로 서 있는 칸
• nx, ny : 다음에 갈 후보 칸 (아직 안 감, 계산만)

nx, ny는 여기로 가도 될까? 하고 찔러보는 용도다. 후보 없이 바로 옮기면 이런 문제가 생긴다.

x = x + dx[d];   // 일단 옮기고 봄
if (막혔나?) ...  // 어? 막혔네... 근데 이미 옮겨버림!

 
막혔는지 확인하기도 전에 넘어가버린다. 벽 밖(n이나 -1)으로 가면 다음 순간 triangle[ny][nx]에서 배열 범위를 벗어나 에러가 난다. 그래서 순서를 이렇게 잡는다.

1. 후보 계산 → nx, ny에 담아둠
2. 검사 → 안전한가? (벽인가? 이미 채운 칸인가?)
3. 안전하면 확정 → x = nx; y = ny;

x = nx; y = ny;에 도달했다는 건 모든 검사를 통과했다는 뜻이다. 첫 방향이 안 막혔거나, 막혔어도 방향 틀어서 갈 곳이 생긴 경우. 어느 쪽이든 보장된 상태다.
한 줄 요약: nx, ny는 가볼까 하는 후보, x = nx; y = ny;는 검사 통과했으니 확정.
 
미리 옮기면 벽 밖으로 나가 에러 나니까 후보 → 검사 → 이동 순서를 지킨다.

 

전체 코드

class Solution {

    private static final int[] dx = {0, 1, -1};
    private static final int[] dy = {1, 0, -1};  // 아래 → 오른쪽 → 왼쪽 위

    public int[] solution(int n) {
        int[][] triangle = new int[n][n];
        int v = 1;          // 채워넣을 숫자
        int x = 0, y = 0;   // 현재 위치
        int d = 0;          // 현재 방향

        while (true) {
            triangle[y][x] = v++;
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) {
                d = (d + 1) % 3;      // 방향 전환
                nx = x + dx[d];
                ny = y + dy[d];
                if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) break;
            }
            x = nx;   // 검사 통과 → 실제 이동
            y = ny;
        }

        int[] result = new int[v - 1];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {  // i행에는 i+1개의 숫자
                result[index++] = triangle[i][j];
            }
        }
        return result;
    }
}

 
 

n=4로 흐름 확인 (두 풀이 공통)

(0,0)에 1 → 아래 계속 → (3,0)에 4
(3,0)에서 아래로 가려니 벽 → 오른쪽으로 틀어 → (3,1)에 5
오른쪽 계속 → (3,3)에 7 → 오른쪽 가려니 벽 → 왼쪽 위로 틀어 → (2,2)에 8
대각선 올라가 (1,1)에 9 → 더 가려니 (0,0)이 이미 1 → 아래로 틀어 → (2,1)에 10
(2,1)에서 아래로 가려니 triangle[3][1]=5(참) → 오른쪽 틀어봐도 triangle[2][2]=8(참) → 종료!

 
결과

1
2  9
3  10 8
4  5  6  7

 
→ [1, 2, 9, 3, 10, 8, 4, 5, 6, 7]

 

마지막 1차원 변환 (두 풀이 공통)

문제는 정답을 1차원 배열로 반환해야 해서, 2차원 삼각형을 순서대로 읽어 펼친다.

int[] result = new int[v - 1];
int index = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {   // i행에는 i+1개의 숫자
        result[index++] = triangle[i][j];
    }
}

• v - 1 : v는 1부터 시작해 마지막에 채운 값 + 1 상태로 끝나므로, 실제 채운 개수는 v - 1개.
• j <= i : 삼각형이라 i번째 행에는 숫자가 i + 1개 있다. (0행 1개, 1행 2개, 2행 3개…)

 

두 방식 비교 & 정리

	풀이 1 (while 3개)	풀이 2 (방향 벡터)
방향 전환	while문을 갈아탐	d = (d+1)%3으로 인덱스만 바꿈
코드 길이	길다	짧다
핵심 아이디어	방향마다 따로 처리	dx/dy + %로 순환
헷갈렸던 점	while 직후 if break;의 역할, break 위치	x=nx; y=ny를 왜 마지막에 하는지

• 두 풀이 모두 큰 그림은 아래 → 오른쪽 → 대각선 위 반복으로 똑같다.
• triangle[...] != 0은 자바 배열이 0으로 초기화된다는 점을 이용해 이미 채운 칸 을 판별한다.
• 풀이 1은 방향마다 while을 나눠 직관적이지만 코드가 길다. 방향 전환용 break는 반드시 최외곽 while(true) 안에 둬야 한다.
• 풀이 2는 dx/dy로 방향을 데이터화하고 %로 순환시켜 훨씬 짧다. "후보 계산 → 검사 → 이동" 순서가 핵심이다.
• 특히 풀이 2의 dx/dy + 후보 검사 패턴은 격자 순회(BFS/DFS) 문제에서 그대로 재사용되니, 익혀두면 계속 써먹을 수 있다.

처음엔 while 3개 방식으로 감을 잡고, 방향 벡터 방식으로 리팩터링해보면 "격자 위 이동"을 다루는 사고방식이 확 정리된다.