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

문제 설명

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

---

나의 풀이

[Python(파이썬)]

import itertools
def solution(n):
    # 2차원 리스트 초기화 하기
    temp = [[0 for _ in range(0, i)] for i in range(1, n+1)]
    # 순서대로 2차원 리스트 채우기
    x, y, num = -1, 0, 1
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            elif i % 3 == 2:
                x -= 1
                y -= 1
            temp[x][y] = num
            num += 1
	# 2차원 리스트 1차원 리스트로 바꾸기
    return list(itertools.chain.from_iterable(temp))

 

---

학습한 내용

풀이 과정
1. 1차원 리스트로 차례대로 채우는 방법 - 화살표 방향 고려 X
2. 2차원 리스트로 차례대로 채우는 방법 - 화살표 방향 고려 0
3. 2차원 리스트 1차원 리스트로 바꾸기

 

1. 1차원 리스트로 차례대로 채우는 방법 - 화살표 방향 고려 X (실패)

 

맨 위 꼭짓점부터 반시계 방향

 

 

처음에는 순서대로 채워갈까 생각(화살표 방향 생각 X)을 하면서 구현을 하기 시작했다. 

 

우선은 수열의 합을 이용해 일차원 배열의 len을 구해 0으로 초기화 했다. 

#수열의 합으로 len 구하기 n(n+1)/2
    nlen = int(n*(n+1)/2)
    answer = [0 for _ in range(nlen)]
    check = 0

 

초기화 한 다음은 화살표 방향은 고려하지 않은 단순히 숫자의 순서만을 고려해 그 상황에서의 화살표 규칙만을 찾아갔다. 

 

1. 첫번째 화살표 <1 ~ n> : 1 2 □ 3 □ □ 4 □ □ □ ... n (□*n-1)       // 규칙 : □가  n뒤에 n-1만큼 채워진다. 

2. 두번째 화살표 <n ~ n*2 -1> : 1 2 □ 3 □ □ 4 □ □ □ ... n (n+1) (n+2) (n+3) (n+4) ... (n*2-1)

// 규칙 : n  ~ (n*2-1) 까지 다 채우기

...

3. 마지막 화살표 

 

    for i in range(1, nlen+1):
        if i <= n:
            answer[check] = i
            if i != n:
                check += i
        elif i < n*2:
            check += 1
            answer[check] = i

 

이렇게 구현하다 보니 모든 화살표의 경우의 수를 다 찾아가며 구현해야하는 그런 효율적이지 못한 코드를 구현하는 듯 했다. 

그래서 도중에 그만두고 다른 방법을 찾았다. 

 

 

 

2. 2차원 리스트로 차례대로 채우는 방법 - 화살표 방향 고려 O

 

1) 밑변의 길이와 높이가 n인 삼각형으로 이차원 리스트를 초기화 한다. 

 

# 이차원 리스트 초기화 하기
temp = [[0 for _ in range(0, i)] for i in range(1, n+1)]

# 출력
[[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

 

2) 화살표가 위, 아래, 옆으로 가는 경우 3가지로 구한다. 

 

for문 과정 (1부터 순서대로 진행된다.) 

 

 

위의 그림과 같이 화살표의 3가지 방향에 따라 인덱스가 달라지는데 이차원 리스트를 temp라 했을때

temp[x][y]라 하면 

 

아래로 가는 화살표 : x의 값 1 증가 

옆으로 가는 화살표 : y의 값 1 증가

위로 가는 화살표 : x의 값 1 감소, y의 값 1 감소

 

for i in range(n):	# 화살표 순서
        for j in range(i, n):	
            if i % 3 == 0:	# 아래로 가는 화살표
                x += 1
            elif i % 3 == 1:	# 옆으로 가는 화살표
                y += 1
            elif i % 3 == 2:	# 대각선 위로 가는 화살표
                x -= 1
                y -= 1
            temp[x][y] = num
            num += 1

 

 

 

 

3. 2차원 리스트 1차원 리스트로 바꾸기

 

[Python] 2차원 리스트를 1차원으로 만들기

 

2차원 리스트를 1차원으로 만드는 다양한 방법

1. sum 함수를 이용한 방법  - sum(리스트명, []) 
2. itertools를 이용한 방법1  - itertools.chain(*iterables)
3. itertools를 이용한 방법2 - itertools.chain.from_iterable(iterables)
4. list comprehension을 이용한 방법 - reduce(집계 함수, iterable 데이터)
5. reduce를 이용한 방법1 - reduce(집계 함수, iterable 데이터)
6. reduce를 이용한 방법2 - reduce + operator

 

다양한 방법을 사용해서 2차원 리스트를 1차원 리스트로 바꾸어 실행 시켜보았다. 

 

sum 

sum 

 

itertools.chain.from_iterable

itertools.chain.from_iterable

 

list comprehension 

list comprehension 

 

reduce 1

reduce 1

 

 

reduce2

reduce2

 

n이 1 이상 1,000 이하의 조건인 이 문제에서는 itertools를 이용한 방법과 리스트 컴프리헨션을 사용한 방법이 가장 시간이 빨랐다. 

 

---

문제 출처

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