프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

⌛ 48분

[나의 풀이]

def down(n,x,y,v,arr):
    
    if x+1<n and arr[x+1][y]!=-1:
        return False,x,y,v,arr
    
    while x+1<n and arr[x+1][y]==-1:
        v += 1
        arr[x+1][y] = v
        x += 1
        
    return True,x,y,v,arr
    
def right(n,x,y,v,arr):

    if y+1<n and arr[x][y+1]!=-1:
        return False,x,y,v,arr
    
    while y+1<n and arr[x][y+1]==-1:
        v += 1
        arr[x][y+1] = v
        y += 1

    return True,x,y,v,arr

def left_up(n,x,y,v,arr):
    
    if x-1<n and y-1<n and arr[x-1][y-1]!=-1:
        return False,x,y,v,arr
    
    while x-1<n and arr[x-1][y-1]==-1:
        v += 1
        arr[x-1][y-1] = v
        x -= 1
        y -= 1

    return True,x,y,v,arr

def solution(n):
    
    if n==1:
        return [1]
    
    answer = []
    arr = [[-1 for i in range(n)] for j in range(n)]
    
    x = 0
    y = 0
    v = 1
    arr[x][y] = v

    while True:
        d_isContinue,x,y,v,arr = down(n,x,y,v,arr)
        if not d_isContinue:
            break
        r_isContinue,x,y,v,arr = right(n,x,y,v,arr)
        if not r_isContinue:
            break
        lu_isContinue,x,y,v,arr = left_up(n,x,y,v,arr)
        if not lu_isContinue:
            break

    for line in arr:
        for x in line:
            if x!=-1:
                answer.append(x)
    
    return answer

정수 n이 주어지고 그림과 같이 길이와 높이가 n인 정삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 숫자를 채워질 때,

첫행부터 마지막행까지 모두 순서대로 합친 배열을 return 하는 문제입니다.

문제에서 제시한 그림은 삼각형이지만 길이가 n인 정사각형 형태의 2차원 배열(arr)을 선언하고 이에 절반에 해당하는 삼각형을 문제에서 제시한 삼각형으로 가정하여 구현하였습니다.

숫자가 채워지는 방식을 자세히 살펴보면, 채워지지 않은 공간까지 (1) 아랫 방향으로 (2) 오른쪽 방향으로 (3) 좌상향 대각선 방향의 순서대로 채워집니다.

이를 구현하기 위해 위 세가지 방식을

def down(n,x,y,v,arr):
    
    if x+1<n and arr[x+1][y]!=-1:
        return False,x,y,v,arr
    
    while x+1<n and arr[x+1][y]==-1:
        v += 1
        arr[x+1][y] = v
        x += 1
        
    return True,x,y,v,arr
    
def right(n,x,y,v,arr):

    if y+1<n and arr[x][y+1]!=-1:
        return False,x,y,v,arr
    
    while y+1<n and arr[x][y+1]==-1:
        v += 1
        arr[x][y+1] = v
        y += 1

    return True,x,y,v,arr

def left_up(n,x,y,v,arr):
    
    if x-1<n and y-1<n and arr[x-1][y-1]!=-1:
        return False,x,y,v,arr
    
    while x-1<n and arr[x-1][y-1]==-1:
        v += 1
        arr[x-1][y-1] = v
        x -= 1
        y -= 1

    return True,x,y,v,arr

각각 정의하였습니다. 또한 다음 채워져야할 숫자가 이미 채워졌을 때 bool형 변수를 return하여 확인하는 방식으로 구현하였습니다.

    while True:
        d_isContinue,x,y,v,arr = down(n,x,y,v,arr)
        if not d_isContinue:
            break
        r_isContinue,x,y,v,arr = right(n,x,y,v,arr)
        if not r_isContinue:
            break
        lu_isContinue,x,y,v,arr = left_up(n,x,y,v,arr)
        if not lu_isContinue:
            break

[다른 사람의 풀이1]

def solution(n):
    res = [[0] * n for _ in range(n)]   # 모두 0으로 개수만큼 세팅
    answer = []
    x, y = -1, 0        # for문 실행시 x값을 처음에 0으로 세팅해주기 위해 초기값은 -1로 세팅
    num = 1             # 들어갈 숫자

    for i in range(n):
        for j in range(i, n):
            # down
            if i % 3 == 0:          # 3으로 퍼센트연산해준 이유는 down/right/up 세 동작이기 때문
                x += 1

            # right
            elif i % 3 == 1:
                y += 1

            # up
            elif i % 3 == 2:
                x -= 1
                y -= 1

            res[x][y] = num        # res에 저장
            num += 1

    for i in res:
        for j in i:
            if j != 0:
                answer.append(j)   # 저장했던 배열 for문이용 합쳐줍니다.

    return answer

'나의 풀이'와 같이 2차원 배열을 활용함과 동시에 (1)down (2)right (3)up 3가지 방식을 나누어 구현하되, 숫자를 채워넣을 때 코드로 표현하는 방식이 훨씬 간결한 풀이입니다.

문제에서 제시한 삼각형은 입력된 n + n-1 + n-2 + ... + 1 개의 칸을 가지는 삼각형으로 이를

    for i in range(n):
        for j in range(i, n):

로 표현하여 채워넣어야하는 경우의 수의 범위를 규정하였습니다.

또한 숫자를 채워나갈 때는, n번까지 down (x+1), n-1번까지 right (y+1), n-2번까지 up (x-1,y-1) ...을 반복하여

    for i in range(n):
        for j in range(i, n):
            # down
            if i % 3 == 0:          # 3으로 퍼센트연산해준 이유는 down/right/up 세 동작이기 때문
                x += 1

            # right
            elif i % 3 == 1:
                y += 1

            # up
            elif i % 3 == 2:
                x -= 1
                y -= 1

            res[x][y] = num        # res에 저장
            num += 1

'달팽이 삼각형'을 완성하는 방식이었습니다.

[다른 사람의 풀이2]

def solution(n):

    triangle = [ [0] * n for _ in range(n) ]
    answer = []
    x, y = -1, 0
    num = 1

    for i in range(n):
        for j in range(i, n):
			
            # Down
            if i % 3 == 0:
                x += 1
			
            # Right
            elif i % 3 == 1:
                y += 1
			
            # Up
            elif i % 3 == 2:
                x -= 1
                y -= 1

            triangle[x][y] = num
            num += 1

    for i in range(n):
        for j in range(i+1):
            answer.append(triangle[i][j])

    return answer

'다른 사람의 풀이1'과 같은 알고리즘이되, 완성한 2차원 배열(triangle)에서 문제에서 제시한 삼각형 내의 숫자만 answer에 append하는 방식만 달랐습니다.

    for i in range(n):
        for j in range(i+1):
            answer.append(triangle[i][j])

감사합니다.