99클럽 코테 스터디 6일차 TIL - 코테에 비슷한 문제가 나왔다.

문제 - 삼각 달팽이 문제링크

오늘 배운 점

어렵게 생각하지 말자

 

문제 설명

이렇게 밑변의 길이와 높이가 n인 삼각형이 테두리부터 시계 반대방향으로 숫자가 1부터 시작해서 1씩 증가하며 채워집니다.

다 채운 후 맨 윗줄부터 정답배열에 넣어 반환하는 문제입니다.

 

접근 과정

결국 n이 주어질 때, 저 삼각형을 어떠한 자료구조에 넣어서 표현한 후 반환하는 문제입니다.

삼각형이라서 헷갈리기 때문에 왼쪽으로 정렬하고 봐 보면, 각 줄을 리스트로 하는 2차원 리스트로 표현할 수 있다고 생각했습니다.

우선 초기값을 모두 0으로 하고 리스트 크기는 1부터 n까지 증가하도록 만들었습니다.

이후 (0, 0)부터 시작해서 한칸씩 전진해나가며 숫자를 채우다가 더이상 못 채우는 조건일 때 끝납니다.

cannotGo = (
    lambda x, y, triangles: x == len(triangles) - 1 or triangles[x + 1][y] != 0,
    lambda x, y, triangles: y == len(triangles[x]) - 1 or triangles[x][y + 1] != 0,
    lambda x, y, triangles: triangles[x - 1][y - 1] != 0
)

def solution(n):
    if n == 1:
        return [1]
    
    answer = []
    # 1. 삼각형을 만든다.
    triangles = [[0 for _ in range(i)] for i in range(1, n + 1)]
    
    dx = [1, 0, -1]
    dy = [0, 1, -1]

    dir = 0
    curX, curY = 0, 0
    num = 1
    while triangles[curX][curY] == 0:
        triangles[curX][curY] = num
        
        if cannotGo[dir](curX, curY, triangles):
            dir = (dir + 1) % len(dx)
        
        curX += dx[dir]
        curY += dy[dir]
        num += 1    
        
    for tri in triangles:
        answer += tri
    return answer

 

여기서 어느 방향으로 전진할지를 결정하는 dir 변수는 매 턴마다 0, 1, 2 중 어느 값인지 결정됩니다. dir 방향으로 갈 수 있는지 cannotGo 가 판단하고, dir를 인덱스로 접근해서 dir에 맞는 람다함수가 선택되어 판단합니다.

판단 결과 dir로 갈 수 없다면 방향이 바뀝니다.

 

이후, while 문에서 triangles[curX][curY] == 0 조건을 통해 이미 채워져있으면 while 문을 중단합니다. 이렇게 작성한 이유는 curX, curY는 매 턴마다 아직 숫자가 작성되어 있지 않다고 예상된 곳으로 가게 되는데, 예상에 맞지 않는 경우는 마지막 순간뿐이기 때문입니다.

 

구한 triangles를 각 행별로 answer에 더해준 후 answer을 반환하였습니다.

 

총평

그림을 보면 우선 담을 공간을 자료구조로 표현하려고 하자.

이후, 수행되어야 할 로직을 매우 작은 단위로 만들자.

n == 1일 때 예외처리를 해줘야 하는 코드라서 완벽하지 않다.