[파이썬] 삼각 달팽이

출처 : programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

 

문제 설명

정수 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]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

♡ 나의 풀이

 

def solution(n):
    answer = []
    _2list=[[0]*n for _ in range(n)]		# 2차원 리스트 생성(n*n)
    x, y=0, -1			# 좌표
    num=1
    for i in range(n):      
        for j in range(i, n):   
            if i%3 == 0:
                y+=1		# 아래
            elif i%3 == 1:
                x+=1		# 오른쪽
            elif i%3 == 2:
                x, y =x-1, y-1	# 위(삼각형이니까 x,y 같이 줄어듦)
            _2list[y][x]=num
            num+=1
    for j in _2list:
        answer+=[i for i in j if i !=0]		# 0은 제외하고
    return answer

_2list=[[0]*n for _ in range(n)] 이 부분을 _2list=[[0]*i for i in range(1, n+1)]로 썼으면 마지막에 if문으로 0 제거 안 해도 됐었는데..

'삼각 달팽이' 문제 풀이는 다른 블로그의 풀이를 참고하였다.

 

inspirit941.tistory.com/287

[Python] 프로그래머스. 삼각 달팽이 (Level 2)

 

이 문제를 푸는 핵심은

1. 2차원 리스트를 만든다

2. 3가지 방향(아래, 오른쪽, 위)를 고려해서 2차원 리스트 행 인덱스를 3으로 나눈 나머지에 따라 값이 저장될 위치가 결정된다.

마지막에 2차원 리스트를 읽을 때 나는 append를 쓰지 않고 answer에 더해나가는 식으로 썼다.

 

 

# 실패
dx = [1, 0, -1]
dy = [0, 1, 0]


def solution(n):
    result = [[0] * i for i in range(1, n + 1)]
    dfs(result, 0, -1, 0, 1, n)
    return sum(result, [])


def dfs(result, d, x, y, i, n):
    nx = x + dx[d]
    ny = y + dy[d]
    if 0 <= nx < len(result) and 0 <= ny < len(result[nx]) and result[nx][ny] == 0 :
        result[nx][ny] = i
        if i == (n+1)*n//2 :
            return
        if d == 2 :     # 위
            dfs(result, d, nx, ny-1, i+1, n)
        else :
            dfs(result, d, nx, ny, i + 1, n)
    else:       # 방향 바꾸기
        d=(d+1)%3
        if d == 1 :     # 오른쪽
            dfs(result, d, nx-1, y, i, n)
        elif d == 2 :   # 위쪽
            dfs(result, d, nx, ny-2, i, n)
        elif d == 0 :
            dfs(result, d, nx+1, ny+1, i, n)

제출하면 4~9까지 런타임 에러 뜬다ㅠㅜㅠㅜㅠㅜㅠ

범위를 벗어나면 방향을 바꿨다.

n=4일 때 10을 못 넣고 끝난다.

dfs보다는 규칙을 찾아서 인덱스에 값을 넣는게 좋은 방법인듯..

 

 

☆ 다른 사람 풀이

def solution(n):
    dx=[0,1,-1];dy=[1,0,-1]
    b=[[0]*i for i in range(1,n+1)]
    x,y=0,0;num=1;d=0
    while num<=(n+1)*n//2:
        b[y][x]=num
        ny=y+dy[d];nx=x+dx[d];num+=1
        if 0<=ny<n and 0<=nx<=ny and b[ny][nx]==0:y,x=ny,nx
        else:d=(d+1)%3;y+=dy[d];x+=dx[d]
    return sum(b,[])

 

d는 dx, dy에서 인덱스.

2차원 리스트 b를 생성할 때 삼각형 형태로 만들고 있다. (나와 달랐던 점)

dx와 dy는 아래, 오른쪽, 위 순으로 담겨있다.

while num<=(n+1)*n//2는 1부터 n까지의 합은 1+(n) = 2+(n-1) = 3+(n-2)...을 이용했다.

n이 4라면 1+4=5고 4의 절반인 2쌍의 합은 각각 5다.

이 계산으로 n 삼각형의 마지막 값이 나온다.

if조건 때문에 이중 반복문이 필요없다. 방향을 바꾼다.

0<=ny<n은 변경된 y 위치가 n행 이상이 될 수 없기 때문이다. (아래 방향 제한) ny<n이라고 해도 된다. 0보다 작아질 일은 없다.

0<=nx<=ny를 0<=nx<n이라고 바꾸면 안 된다. (위, 오른쪽 방향 제한) b리스트의 모든 인덱스는 행<=열이다.

b[ny][nx]==0을 빼면 기대한 값과 다르게 나온다. 값을 넣었던 곳에 다른 값을 덮어씌울 수 있으므로 꼭 써야한다.

 

if조건이 true가 아닐 경우 d+1을 3으로 나눈 나머지를 이용한다. d+1을 해야 방향이 바뀐다.

마지막에 return으로 sum()함수를 사용한 게 신기했다. 2차원 리스트 b의 값들을 1차원 리스트로 바꾼 결과를 얻는다. 

파이썬 document를 보니 itertools.chain()도 이와 같이 쓸 수 있다.

 

docs.python.org/3/library/functions.html?highlight=sum#sum

Built-in Functions — Python 3.9.0 documentation

 

# 정리

이중반복문 안 쓰고 싶다면 if문으로 모든 조건 줄 수 있음.

비슷한 문제를 좀 더 풀어서 완전히 익혀야겠다.

 

 

 

문제 출처 👉 프로그래머스