재귀 파이썬 문제 삼각달팽이 프로그래머스 코딩테스트 (6)

목차

서론

지난번 포스팅에 이어 이번에는 난이도가 있는 재귀 문제를 풀어보고자 한다. 삼각달팽이라는 문제로 프로그래머스에 있다. 문제 제목과는 다르게 예시부터 난이도가 있어보이는 생김새다. 아무튼 이번 포스팅에서는 해당 문제를 풀어보고 그 과정에 대해서 얘기하고자 한다. 설령 못풀어도 다른 사람 풀이 참고하는 한이 있어도 어떻게서든지 풀어볼 예정이다.

---

 

재귀 문제 다른 사람 풀이 분석

풀이 방법을 엄청 생각해봤으나 도저히 재귀로 풀리지가 않아 다른 사람 풀이를 검색해봤다. 아니나 다를까 재귀로 푼사람은 거의 없었고, 재귀로 풀었다는 사람 보면 되게.. 복잡했다. 재귀 강의에서 for문과 재귀는 서로 왔다갔다할 수 있지만, 코드 복잡도와 돌아가면서 생기는 불필요한 메모리의 등가교환이라고 말했는데(내가 의역함ㅋㅋ.) 재귀를 쓴 코드를 보면 코드의 간결성도 메모리도 얻는게 하나 없었다. 아무튼 다른 사람의 코드를 보고 이 문제를 어떻게 풀어야 될 지 분석해봤다. 크게 아이디어를 잡자면 삼각형 좌표를 옮길때마다 cnt 값을 넣는거다. cnt는 +1씩만 하면 되기에 삼각형 좌표를 파악하는게 핵심.

def solution(n):
    answer = []
    l = [[0]*i for i in range(1, n+1)]
    y,x = -1,0 
    cnt = 1
    for i in range(n):
        for _ in range(i,n):
            if i % 3 == 0: 
                y += 1 
            elif i% 3 == 1: 
                x += 1 
            elif i% 3 == 2:
                x -= 1
                y -= 1
            l[y][x] = cnt
            cnt+=1 
            
    for i in _list:
        for j in i:
            answer.append(j)
            
    return answer

• 삼각형 선언(혹은 2차원 배열)
• x = -1, y = 0 , res에 저장할 수 num을 선언 및 초기화한다. x,y는 매트릭스 위치를 표현하는 좌표다. y를 0이 아닌 -1로 한 이유는 for문 첫번째 실행이 무조건 아래로 숫자를 채우는 형식이기 때문이다.
• 규칙상, 행의 수 만큼 방향을 튼다. i % 3 == 0이면 아래 방향, == 1이면 오른쪽 방향, ==2이면 위 방향
• 이중 for문으로 한변을 지날때마다  4개~ 1개로 저장할 수가 적어지니 0~n까지, i~n까지의 이중 for문 작성.
• 알맞은 인덱스에 num을 1씩 늘리며 저장한다.
• answer에 append해서 저장한다.

---

끝으로

사실 약 이틀간 골똘히 생각해본 재귀풀이법을 ...결국 이루지 못했다. 허지만 이런 구현도 있다는 것을 알게됐음에 감사함을 남기며 이만 포스팅을 마치겠다. 다음 포스팅에는 그리디 관련 이론 요약과 문제 포스팅을 할 예정이다. 많관부.