[ 프로그래머스 [ 월간코드챌린지 ] 삼각 달팽이 ] (C++)

프로그래머스의 삼각 달팽이(월간 코드 챌린지) 문제이다.

[ 문제풀이 ]

규칙에 맞게 숫자를 채워넣었을 때, 최종적인 상태를 구해야 하는 문제이다.

접근하는 방법부터 풀이까지 순차적으로 알아보도록 하자.

#1. 진행방향

본인은 숫자가 채워지는 방향을 크게 3가지 상태로 나눠서 관리해 주었다.

1. 아래로 내려가는 경우

2. 오른쪽으로 움직이는 경우

3. 위쪽으로 올라가는 경우

이렇게 3가지 상태로 나눠주었다. 다음은 n = 5 인 예시이다.

.

위와 같은 삼각형이 있을 때, 숫자를 채우는 과정을 화살표로 표시해보면 다음과 같다.

.

가장 처음에 빨강색 화살표 처럼 "가장 왼쪽 줄을 위에서 아래로 내려오면서 숫자를 채우는 과정" 을 진행하게 된다.

두 번째로는 파랑색 화살표 처럼 "가장 아랫 줄을 왼쪽에서 오른쪽으로 움직이면서 숫자를 채우는 과정" 을 진행하게 된다.

세 번째로는 주황색 화살표 처럼 "가장 오른쪽 줄을 아래에서 위로 올라가면서 숫자를 채우는 과정" 을 진행하게 된다.

위의 그림을 이어서 숫자를 채우는 과정을 그려보면...

.

위의 그림과 같이 2번의 과정을 더 진행하면 모든 삼각형을 채울 수 있게 된다.

그런데 보면 계속해서 동일한 패턴이 반복되어진다.

빨강색 화살표 → 파랑색 화살표 → 주황색 화살표 → 빨강색 화살표 → 파랑색 화살표... 이런식으로 !

따라서 본인은 숫자를 채워가는 과정을 3가지로 나눠주었다.

1. 빨강색 화살표처럼, "위에서 아래로 내려오는 경우"

2. 파랑색 화살표처럼, "왼쪽에서 오른쪽으로 움직이는 경우"

3. 주황색 화살표처럼, "아래쪽으로 위쪽으로 올라가는 경우"

이 3가지 과정을 계속해서 반복해 주었다.

#2. 반복 횟수

1번 과정에서 3가지 과정을 계속해서 반복해 주었다고 했는데 언제까지 반복을 해야할까 ??

본인은 이를 정하기 위해서 "삼각형에 들어있는 가장 큰 숫자"를 계산해 주었다.

다음은 n = 4 인 삼각형과, n = 5 인 삼각형을 모두 채웠을 때의 형태이다.

.

위의 삼각형들에서 '가장 큰 숫자'는 빨강색으로 표시해 주었다.

n = 4인 경우에는 '10' 이고, n = 5인 경우에는 '15'가 된다.

이 숫자들은 주어진 n을 등차수열로 나타냈을 때의 결과값들이 된다.

n = 4인 경우, 1 + 2 + 3 + 4 = 10 이고, n = 5인 경우, 1 + 2 + 3 + 4 + 5 = 15가 된다.

따라서, 우리는 n 이 주어진다면, 해당 삼각형에 들어가는 가장 큰 숫자는 (n * (n + 1)) / 2 가 된다.

본인은 위의 3가지 과정을 반복하면서 삼각형에 숫자를 1부터 하나씩 채워넣어주었는데, 이 때, 채워넣는 숫자가

(n * (n + 1)) / 2보다 작거나 같을 때 까지만 반복해 주었다.

#3. 움직이는 횟수 정하기

이 문제의 핵심이라고 할 수 있는 부분이다. 어떤 방향으로 언제까지 움직일지는 위에서 모두 정했고, 이제 실제로 얼마만큼을 움직여야 하는지를 구해보자. 지금부터는 위에서 설명했던 대로, 화살표의 색깔로 움직이는 방향을 표현하겠다.

↙ 빨강색 화살표 : 가장 왼쪽 줄을 위에서 아래로 내려오는 방향으로 채우는 상태

→ 파랑색 화살표 : 가장 아랫줄을 왼쪽에서오른쪽으로 움직이는 방향으로 채우는 상태.

↖ 주황색 화살표 : 가장 오른쪽 줄을 아래에서 위로 올라가는 방향으로 채우는 상태.

사실 위의 표현들을 굉장히 모호한 표현들이다.

먼저, 애매한 이유들을 빨강색 화살표를 예시로 들어보겠다. 아까처럼 n = 5인 삼각형을 채우는 순서이다.

.

.

먼저 윗줄에 3개의 그림을 1, 2, 3번 아랫줄에 2개의 그림을 4, 5번으로 번호를 붙여서 표현하겠다.

↙ 빨강색 화살표 : 가장 왼쪽 줄을 위에서 아래로 내려오는 방향으로 채우는 상태

먼저, 1번 그림에서 빨강색 화살표는 위에서 언급한 정의와 동일하다.

실제로 주어진 삼각형에서 가장 왼쪽줄을 위에서 아래로 내려오는 방향으로 채우는 상황이 맞다.

그런데, 4번 그림을 한번 보자.

과연, 저게 실제로 주어진 삼각형에서 가장 왼쪽줄을 채우고 있는 상황일까 ?? 그건 아니다. 조금 더 정확하게 말해보자면

가장 왼쪽줄보다 한칸 오른쪽에 있는 줄을 채우는 상황이고, 더해서 가장 아랫줄까지 내려가지도 않는다.

중간 어느 지점부터 어느지점까지만 내려간다는 것이다.

그래서 지금부터는 현재 특정 색깔의 화살표를 진행할 차례인데, 어느 지점부터 어느지점까지 숫자를 채워야 하는지에 대해서 알아보자.

지금부터는 4가지 변수들을 이용해서 접근할 것인데, 변수들의 값을 설정하는 기준은 "아직 채워지지 않은 칸"을 기준으로 설정해주었다. 먼저 4가지 변수들에 대해서 알아보자.

바로, Top, Bottom, Left, Right 이다. 변수들의 이름이 곧 나타내는 위치이고, 위에서 말했듯이 아직 채워지지 않은 칸을 기준으로 값들을 설정해 주었다. 그리고 삼각형은 쉽게, 가장 위에 '1'이 있는 층을 1층, 가장 아래에 n개가 있는 층을 n층이라고 표현하겠다.

- Top : 아직 채워지지 않은 가장 윗 줄을 의미한다.

- Bottom : 아직 채워지지 않은 가장 아랫줄을 의미한다.

- Left : 아직 채워지지 않은 가장 왼쪽줄을 의미한다.

- Right : 아직 채워지지 않은 가장 오른쪽 줄을 의미한다.

위의 정의처럼 변수들을 생각하면 굉장히 단순하고 좋았겠지만, 저 중에 딱 한 가지 변수가 굉장히 애매하다.

바로 'Right'변수이다. 왜 애매할까 ?? 사실 그림으로만 본다면 애매한 부분이 없지만, 실제로 위의 삼각형을 2차원 배열로 표현해서 코드적으로 숫자를 채우는 과정을 생각해보자. 위의 삼각형은 단순하게 2차원 배열로 표현할 수 있다.

n = 5인 경우를 2차원 배열로 표현해보면 다음과 같다.

.

위와 같이 표현될 것이다. 그럼, 이 상태에서 "가장 오른쪽 줄" 이 어디일까 ??

그림에서 보면 알 수 있듯이, 각 행마다 가장 오른쪽에 대한 위치(열의 크기)가 다르다.

1행에서는 가장 오른쪽 열은 1열이고, 2행에서는 가장 오른쪽 열은 2열이고, 3행에서는 가장 오른쪽 열은 3열이고, n행에서 가장 오른쪽 열은 n열이다. 즉 ! 단순하게 "아직 채워지지 않은 가장 오른쪽 줄은 n번째 열입니다." 라고 표현을 할 수가 없다는 것이다. 그래서 본인은 이 Right라는 변수에 대해서만 다음과 같이 생각하고 구현해 주었다.

- Right : 현재 까지 채운 오른쪽 줄의 횟수

정확하게 이해하지 못했더라도, 계속해서 진행해보자.

그럼 초기값을 설정해보자.

Top : 아직 채워지지 않은 가장 윗줄을 의미한다. 초기에는 아직 아무런 숫자들도 채워지지 않은 상태이기 때문에, Top = 1 이 된다.

Bottom : 아직 채워지지 않은 가장 아랫줄을 의미한다. Bottom = n.

Left : 아직 채워지지 않은 가장 왼쪽줄을 의미한다. Left = 1.

Right : 현재까지 채운 오른쪽 줄의 횟수는 0회이다. 아직 아무런 숫자들도 채워지지 않은 상태이기 때문에, 현재까지 채운 오른쪽 줄의 횟수는 0회이다.

[ Top , Bottom , Left , Right ] = [ 1 , n , 1, 0 ]

이제 빨강색, 파랑색, 주황색 화살표 순서대로 채워보자. 다시한번 화살표들의 정의를 적어보자.

↙ 빨강색 화살표 : 가장 왼쪽 줄을 위에서 아래로 내려오는 방향으로 채우는 상태

→ 파랑색 화살표 : 가장 아랫줄을 왼쪽에서오른쪽으로 움직이는 방향으로 채우는 상태.

↖ 주황색 화살표 : 가장 오른쪽 줄을 아래에서 위로 올라가는 방향으로 채우는 상태.

지금부터 n = 5 인 경우를 함께 채워보자.

가장 처음 빨강색 화살표는 어디서 부터 어디까지 내려와야할까 ?? 바로, Top부터 Bottom까지 내려오면 된다.

Top부터 Bottom까지 내려오면서, 어디에 있는 칸들을 채워줘야할까 ? 바로 Left에 있는 값들이다.

그럼 Top = 1 이고, Bottom = n 이고, Left = 1이니, 주어진 맵에서 (1, 1) , (2, 1), ~ (5, 1)까지의 값들이 채워질 것이다.

그림으로 나타내면 다음과 같이 삼각형이 채워지게 된다.

.

그럼 이렇게 진행을 하고 난 후에 변수들의 값들을 생각해보자.

Top : 아직 채워지지 않은 가장 윗 줄이다.

그런데, 우리는 빨강색 화살표를 한번 진행하고 났더니, 1층은 모두 채워졌다.(1층은 1하나만 채우면 모두 채워지는 층이므로) 그럼, 아직 채워지지 않은 가장 윗줄은 ? 2층이 된다. 즉, 빨강색 화살표를 진행 후에 Top의 값은 ++가 된다.

또한, 빨강색 화살표를 진행하고 났더니, 가장 왼쪽줄이 또 다 채워졌다.

그럼, 아직 채워지지 않은 갖아 왼쪽줄은 ? 2번째 줄이 된다. 즉, 빨강색 화살표를 진행 후에 Left의 값은 ++가 된다.

[ Top , Bottom , Left , Right ] = [ 2 , n , 2 , 0 ]

그리고 가장 중요한 것 ! 빨강색 화살표 다음엔 ? 파랑색 화살표를 진행하면 된다. 그 다음 진행해야 할 화살표가 파랑색이라고 체크를 해주어야 한다.

↙ 빨강색 화살표 방향으로 맵 채우기

1. Top ~ Bottom 방향으로 진행 된다.

2. Top ~ Bottom 방향으로 진행될 때, 실제로 채우는 칸은 Left 칸을 채우게 된다.

3. 한번 진행한 후에는, Top과 Left의 값이 ++ 되어진다.

그럼 파랑색 화살표를 진행해보자. 파랑색 화살표는 왼쪽에서 오른쪽으로 숫자들을 채워가는 과정이다. 그런데 어디까지 채워야할까 ?? 일단 "현재 채워지지 않은 가장 아랫줄을 채워야 하는 것"은 알 것 같다. 그럼, "현재 채워지지 않은 가장 아랫줄은 Bottom에 저장" 되어 있으므로, Bottom 층을 채워주면 될 것 같다. 근데 어디서 부터 어디까지 채워줘야할까 ??

바로, Left부터 Bottom - Right까지 채워주면 된다.

왜그럴까 ?? 일단, 시작점이 Left인 것은 왜 인지 알 것 같다. 아직 채워지지 않은 가장 왼쪽 줄부터, 오른쪽으로 쭉 가면서 채워주면 되는 거니까 ! 그럼 Bottom - Right의 의미는 ? 먼저, 파랑색 화살표는 "아직 채워지지 않은 가장 아랫줄을 채우기 위한 화살표" 이다. 즉 ! 현재 설정되어 있는 Bottom을 채우는 것이 맞다. 그런데, 오른쪽 줄이 현재까지 몇 번 채워져 있냐에 따라서 얼마만큼을 채우는지가 달라진다.

. .

이렇게 위의 2가지 경우가 채우는 정도가 다르다는 것이다.

그 정도는 어느정도일까 ? 바로, "지금까지 오른쪽 줄을 채운 횟수를 빼버린 칸 까지만 채워주면 되는 것" 이다.

실제로 위의 그림에서 왼쪽 그림은, 아직 오른쪽 줄이 하나도 채워지지 않았기 떄문에, 가장 오른쪽 줄 까지 파랑색 화살표가 진행되고 있지만, 오른쪽 그림은, 기존의 단계에서 주황색 화살표에 의해서 가장 오른쪽 줄이 1회 채워졌기 때문에, 그 1회만큼을 뺀 칸까지만 채우는 것이다.

즉, 파랑색 화살표는, Left 부터 Bottom - Right까지 진행되어 진다.

그럼 숫자를 한번 직접 채워보자.

.

이렇게 숫자가 채워졌다. 그럼 이제는 어떤 변수값들이 변하게 될까 ??

채워지지 않은 가장 아랫줄, 즉, Bottom의 값이 초기에 n이였지만, 파랑색 화살표를 통해서 가장 아랫층이 채워졌다.

즉, 채워지지 않은 가장 아랫줄이 한칸 위로 올라가게 된다. 즉 ! Bottom의 값은 --가 된다.

→ 파랑색 화살표 방향으로 맵 채우기

1. 현재 채워지지 않은 가장 아랫줄(Bottom) 에서 진행 된다.

2. 실제로 채워지는 칸은, Left ~ Bottom - Right 칸을 채우게 된다.

3. 한번 진행한 후에는, Bottom의 값이 -- 되어진다.

이제 주황색 화살표를 진행해보자.

먼저 주황색 화살표는 어느 방향으로 진행될까 ? 아랫줄에서 위쪽으로 올라가는 방향이기 떄문에, 아마 Bottom ~ Top의 방향으로 진행될 것이다. 그럼 실제로 채워지는 칸은 어디일까 ??

바로, "현재 층에서, 아직 채워지지 않은 가장 오른쪽 칸"을 채우게 된다.

여기서는 조금 특이하게 "현재 층에서" 라는 표현이 등장한다. 왜그러냐면, 위에서 언급했듯, 각 층마다 가장 오른쪽 칸이 다르기 때문이다. 1층의 가장 오른쪽 칸 = 1 , 2층의 가장 오른쪽 칸 = 2, 3층의 가장 오른쪽 칸 = 3 이런식으로..

따라서, "현재 층에서, 아직 채워지지 않은 가장 오른쪽 칸" 이라는 것은, "현재 층수 - 현재까지 오른쪽 라인을 채운 횟수" 가 된다. 예를들어서 아직까지 오른쪽 라인을 한번도 채우지 않았다고 가정해보자. 그리고 현재 4층을 채울려고 한다.

그럼, 4층에 4번째 칸이 채워질 것이다. 즉, 4 - 0 이 되는 것이다. 그럼 그 다음 한 턴이 돈 후에, 다시 주황색 화살표로 돌아왔을 때는 어디를 채우게 될까 ? 4층에 3번칸을 채우게 될 것이다. 왜? 4층에서 현재 까지 오른쪽 라인을 채운 횟수가 1회이기 떄문에, 4 - 1 = 3. 이런식으로 채우게 될 것이다.

그럼 숫자를 한번 채워보자. 채워보면 다음과 같이 될 것이다.

.

그럼 어떤 변수에 어떤 변화가 일어나게 될까 ??

모든 층에, 가장 오른쪽 줄이 채워지게 된 것을 확인할 수 있다. 즉, 현재까지 오른쪽 줄을 채운 횟수가 증가할 것이다.

즉, Right 변수의 값이 ++ 되어질 것이다.

또 한가지 변화가 더 있다. 주황색 화살표를 진행했더니, 2층까지 모두 채워졌음을 확인할 수 있다.

즉 ! 아직 채워지지 않은 가장 윗줄을 의미하는 Top의 값이 ++ 되어지게 된다.

↖ 주황색 화살표 방향으로 맵 채우기

1. Bottom ~ Top의 방향으로 진행하게 된다.

2. 실제로 채워지는 칸은, "현재 층수 - 현재까지 오른쪽 줄을 채운 횟수" 의 연산으로 나온 칸을 채우게 된다.

3. 한번 진행한 후에는, Right와 Top의 값이 ++ 가 되어진다.

이렇게 위의 3가지 과정을 계속해서 반복해준다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(int n)
{
    vector<vector<int>> MAP(n + 1, vector<int>(n + 1));
    vector<int> answer;
    int Max_Num = (n * (n + 1)) / 2;
    int Top = 1;
    int Bottom = n;
    int Left = 1;
    int Right = 0;
    int Num = 1;
    int State = 0;
    while (Num <= Max_Num)
    {
        if (State == 0)
        {
            for (int i = Top; i <= Bottom; i++) MAP[i][Left] = Num++;
            Top++;
            Left++;
            State = 1;
        }
        else if (State == 1)
        {
            for (int i = Left; i <= Bottom - Right; i++) MAP[Bottom][i] = Num++;
            Bottom--;
            State = 2;
        }
        else if (State == 2)
        {
            for (int i = Bottom; i >= Top; i--) MAP[i][i - Right] = Num++;
            Right++;
            Top++;
            State = 0;
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            answer.push_back(MAP[i][j]);
        }
    }
    
    return answer;
}