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

chanyeong kim·2022년 1월 18일

목록 보기

45/51

vue image

📩 -->문제설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

💡 solution(사용언어: python)

def solution(n):
    check = [[0] * n for _ in range(1, n+1)]
    
    x, y = -1, 0
    num = 1
    
    for i in range(n):
        for _ in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            else:
                x -= 1
                y -= 1

            check[x][y] = num
            num += 1
        
    return [j for i in check for j in i if j != 0]

👉 설명

삼각형이 만들어지는 패턴을 보면 위 그림과 같은 순서대로 삼각형이 만들어지는데 자세히 보면, 6 - 5 - 4 - 3 - 2 - 1로 하나씩 줄어든다.
즉, n이 입력되면 n - (n-1) - (n-2) ............. 2 - 1 식으로 줄어드는 것을 알 수 있다.
그래서 길이가 n인 리스트를 만들고, 리스트의 원소들을 다시 길이가 n인 리스트로 구성을 해준 뒤 순차적으로 채워주면 된다.
- n이 6라면 아래와 같은 형태의 리스트를 만들고 해당 좌표에 값을 채워준다.
- ```
[[0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0]] 
```
x: 위에서 아래로, y: 왼쪽에서 오른쪽으로
좌표를 지정해줄 때 일정한 규칙이 존재하는데, 리스트의 [0][0]의 값을 1로 채워주고 [1][0]을 2로 채워주고 [5][0]의 값을 6으로 채워주는 것은 [x][y]에서 x 좌표의 값을 1씩 더해주면 되었다.
그런데 7을 추가하기 위해서는 [x][y] 중 y 좌표의 값을 1 더해주어야한다.
다시 12를 추가하기 위해서 [x][y]에서 x와 y 좌표 모두 -1을 해주어야 한다.
여기서 일정한 규칙이 존재하는데, 위의 그림의 순서대로 1번 - 2번 --- 6번 중 동일하게 꺽이는 숫자들은 3으로 나누었을 때 나머지가 같은 것을 이용하였다.

       for i in range(n):
        for _ in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            else:
                x -= 1
                y -= 1

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

결과적으로 check는 아래와 같이 생성된다.

[[1, 0, 0, 0, 0, 0],
[2, 15, 0, 0, 0, 0],
[3, 16, 14, 0, 0, 0],
[4, 17, 21, 13, 0, 0],
[5, 18, 19, 20, 12, 0],
[6, 7, 8, 9, 10, 11]]

이후 0을 제거해주고 순서대로 합쳐주면 된다!

💡 Solution 보완

def solution(n):
    check = [[0] * _ for _ in range(1, n+1)]
    
    x, y = -1, 0
    num = 1
    
    for i in range(n):
        for _ in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            else:
                x -= 1
                y -= 1

            check[x][y] = num
            num += 1
        
    return [j for i in check for j in i]

처음에 check 리스트를 생성해줄 때 각각 요소 리스트의 길이를 n으로 맞춰주었는데 위에서부터 값을 채우기 때문에 굳이 그럴필요가 없었고 수정해주었다.
결과적으로 효율성이 조금 상승했다.

다른풀이

def solution(n):
    check = [[0] * _ for _ in range(1, n+1)]
    
    x, y = -1, 0
    num = 1
    
    for i in range(n):
        for _ in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            else:
                x -= 1
                y -= 1

            check[x][y] = num
            num += 1
        
    return sum(check, [])