[프로그래머스] Lv2. 삼각 달팽이

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

프로그래머스

 

문제

 

예시

 

입출력

 

제한 사항

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

 

처음 시도

def solution(n):
    # n개의 빈 리스트를 생성한다.
    answer = [[] for _ in range(n)]

    # 채워진 배열을 나타내는 리스트
    full = [False for _ in range(n)]

    # 젤 아래 리스트를 나타내는 수
    ground = n - 1

    # 위로 갈지(1), 아래로 갈지(0), 가만히(2)
    dir = 0

    # 값은 1부터 시작
    curr = 1

    # 인덱스는 0부터 시작
    idx = 0

    # 모든 수가 포함되었을 경우 종료
    while curr <= n * (n + 1) // 2:

        # 값을 채우기 전에 리스트가 전부 찼는지 확인하기
        if full[idx]:
            # 찼으면 원리 내려가던 중이면 올리기
            if dir == 0:
                idx -= 1
                dir = 1

            # 원래 올라가던 중이면 내리기
            else:
                idx += 1
                dir = 0


        # 전부 찬게 아니라면
        else:
            # 1. ground 인덱스라면 len(answer[ground]) == ground + 1 될때까지 curr 채우기
            if idx == ground:
                while len(answer[idx]) < idx + 1:
                    answer[idx].append(curr)
                    curr += 1
                full[idx] = True
                idx -= 1
                dir = 1
                continue

            # 2. 값을 채우면서 인덱스 내려가도록 하기
            elif dir == 0:
                answer[idx].append(curr)
                idx += 1

            # 3. 값을 채우면서 인덱스 올라가도록 하기
            elif dir == 1:
                answer[idx].append(curr)
                idx -= 1

            # 4. 값 올려주기
            curr += 1

    return sum(answer, [])

먼저 위 코드는 테스트를 통과하지 못하였다.

그러나, 위 코드의 접근 방식 중에서도 올바른 접근은 있다.

1. n개의 빈 리스트를 생성한 것
2. 1부터 n*(n+1)//2 까지의 수를 while 문을 통해 현재 값을 1씩 증가시키며 값을 append 하고 n*(n+1)//2 의 수까지 append 된 이후에 종료하는 것
3. 어쨋든 방향의 값을 변동시켜 인덱스를 증가 또는 감소 시켜 값을 저장하려 했던 것

 

다만, 함께 공부하는 다른 사람들의 풀이를 듣고 고쳐야 할 점이 많이 있었다. 

• 방향 전환을 처리하는 조건을 잘못 설정하였다.→ 위/아래 방향만 처리하는 것이 아닌 위/아래/오른쪽 방향을 순차적으로 변경해야 한다.

생각해보면 2차원 리스트를 생각할 때, 1차원 배열씩 하나로 묶어서 생각하였기 때문에 오른쪽으로 인덱스를 이동해야 한다는 사실을 생각하지 못했던 것이다. 그러나 2차원 배열은 [i][j] 처럼 2개의 인덱스로 좌표를 이동할 수 있다는 것을 생각해야 한다. 당연해 보이지만 관점에 따라 달라질 수 있어 조심해야겠다고 생각했다.

• 모든 리스트가 채워졌는지 확인하는 리스트는 필요하지 않다.

 

해결

def solution(n):
    # n*n 크기의 2차원 배열 생성 후 0으로 초기화
    matrix = [[0]*n for _ in range(n)]
    # 시작 위치와 방향, 현재 숫자 초기화
    x, y = -1, 0
    number = 1
    # 아래, 오른쪽, 대각선 위 이동을 위한 방향 벡터 설정
    dx = [1, 0, -1]
    dy = [0, 1, -1]
    
    # 각 변의 길이를 설정
    for i in range(n):
        for j in range(i, n):
            # 방향 전환: 아래 -> 우 -> 상 -> 아래 ... 순으로 반복하므로, 3으로 나눈 나머지를 이용
            nx = x + dx[i % 3]
            ny = y + dy[i % 3]
            # 다음 위치에 현재 숫자를 채우고, 현재 숫자를 1 증가
            matrix[nx][ny] = number
            number += 1
            # 위치 업데이트
            x, y = nx, ny
    # 2차원 배열을 1차원 리스트로 변환하여 반환
    answer = [x for row in matrix for x in row if x != 0]
    return answer

1. n 크기의 이차원 리스트를 준비하고, 모든 값을 0으로 초기화한다.

2. 처음 시작 위치를 (x, y) = (-1, 0)으로 설정한다. 이는 다차원 리스트에서 아직 시작 위치에 도달하지 않았음을 의미한다.

3. 다음 위치 계산을 위한 방향 벡터 dx, dy를 이용해 위/아래/오른쪽으로 이동하는 로직을 반영한다.

4. 각 단계에서 현재 방향에 맞게 위치를 업데이트 하면서 숫자를 채워넣는다.

5. 반복문을 통해 삼각형을 채워나가면서, 마지막으로 2차원 배열에 채워진 값을 조건 리스트 내포를 사용해 1차원 리스트로 변환하여 반환한다.