프로그래머스 기초 Day 25 파이썬

프로그래머스

정수를 나선형으로 배치하기

문제 설명

양의 정수 n이 매개변수로 주어집니다.

n × n 배열에 1부터 n^2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

제한사항

• 1 ≤ n ≤ 30

입출력 예

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

입출력 예 설명

입출력 예 #1

• 예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.

행 \ 열	0	1	2	3
0	1	2	3	4
1	12	13	14	5
2	11	16	15	6
3	10	9	8	7

따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.

 

입출력 예 #2

• 예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.

행 \ 열	0	1	2	3	4
0	1	2	3	4	5
1	16	17	18	19	6
2	15	24	25	20	7
3	14	23	22	21	8
4	13	12	11	10	9

따라서 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]를 return 합니다.

문제 분석

의사 코드(pseudo code)
1 n × n 크기의 이차원 배열을 0으로 초기화
2 방향을 오른쪽, 아래, 왼쪽, 위(시계 방향) 순서로 설정
3 초기 위치 (0, 0)
4 1부터 n^2까지 반복하면서
  a 현재 위치에 숫자를 채움
  b 다음 위치를 계산
  c 다음 위치가 범위를 벗어나거나 이미 값이 채워져 있으면 방향을 전환
  d 방향에 맞게 다음 위치로 이동
5 배열 반환

solution.py

def solution(n):
    # n × n 배열 초기화
    answer = [[0] * n for _ in range(n)]
    
    # 방향 : 오른쪽, 아래, 왼쪽, 위
    dx = [0, 1, 0, -1] # 행 이동
    dy = [1, 0, -1, 0] # 열 이동
    dir = 0            # 초기 방향은 오른쪽
    
    x, y = 0, 0        # 시작 위치
    for num in range(1, n * n + 1):
        answer[x][y] = num # 현재 위치에 숫자를 채움
        
        # 다음 위치 계산
        nx = x + dx[dir]
        ny = y + dy[dir]
        
        # 경계 조건이나 이미 채워진 곳이면 방향 전환
        if nx < 0 or nx >= n or ny < 0 or ny >= n or answer[nx][ny] != 0:
            dir = (dir + 1) % 4
            nx = x + dx[dir]
            ny = y + dy[dir]
            
        x, y = nx, ny # 방향에 맞게 다음 위치로 이동
        
    return answer

복잡도 분석

반복문을 통해 배열을 채우는 과정은 n × n번 반복되므로 시간 복잡도는 O(N^2)입니다.
배열 접근 및 계산 작업의 시간 복잡도는 O(1)입니다.
n × n 크기의 배열이 생성되므로 공간 복잡도는 O(N^2)입니다.
dx, dy, x, y, dir 등의 상수 크기 변수들의 공간 복잡도는 O(1)입니다.
따라서 최종 시간 복잡도와 공간 복잡도는 O(N^2)입니다.

---

특별한 이차원 배열 2

문제 설명

n × n 크기의 이차원 배열 arr이 매개변수로 주어질 때, arr이 다음을 만족하면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

• 0 ≤ i, j < n인 정수 i, j에 대하여 arr[i][j] = arr[j][i]

제한사항

• 1 ≤ arr의 길이 = arr의 원소의 길이 ≤ 100
• 1 ≤ arr의 원소의 원소 ≤ 1,000
• 모든 arr의 원소의 길이는 같습니다.

입출력 예

arr	result
[[5, 192, 33], [192, 72, 95], [33, 95, 999]]	1
[[19, 498, 258, 587], [63, 93, 7, 754], [258, 7, 1000, 723], [587, 754, 723, 81]]	0

입출력 예 설명

입출력 예 #1

• 예제 1번에서 문제의 조건이 잘 보이도록 표를 만들면 다음과 같습니다.

i	j	arr[i][j]	arr[j][i]
0	0	5	5
0	1	192	192
0	2	33	33
1	0	192	192
1	1	72	72
1	2	95	95
2	0	33	33
2	1	95	95
2	2	999	999

조건을 만족하므로 1을 return 합니다.

 

입출력 예 #2

• 예제 2번의 arr에서 arr[0][1] = 498 ≠ 63 = arr[1][0]이므로 조건을 만족하지 않습니다. 따라서 0을 return 합니다.

solution.py

def solution(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            if arr[i][j] != arr[j][i]:
                return 0
    return 1

---

정사각형으로 만들기

문제 설명

이차원 정수 배열 arr이 매개변수로 주어집니다.

arr의 행의 수가 더 많다면 열의 수가 행의 수와 같아지도록 각 행의 끝에 0을 추가하고, 열의 수가 더 많다면 행의 수가 열의 수와 같아지도록 각 열의 끝에 0을 추가한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

제한사항

• 1 ≤ arr의 길이 ≤ 100
• 1 ≤ arr의 원소의 길이 ≤ 100
  • arr의 모든 원소의 길이는 같습니다.
• 1 ≤ arr의 원소의 원소 ≤ 1,000

입출력 예

arr	result
[[572, 22, 37], [287, 726, 384], [85, 137, 292], [487, 13, 876]]	[[572, 22, 37, 0], [287, 726, 384, 0], [85, 137, 292, 0], [487, 13, 876, 0]]
[[57, 192, 534, 2], [9, 345, 192, 999]]	[[57, 192, 534, 2], [9, 345, 192, 999], [0, 0, 0, 0], [0, 0, 0, 0]]
[[1, 2], [3, 4]]	[[1, 2], [3, 4]]

입출력 예 설명

입출력 예 #1

• 예제 1번의 arr은 행의 수가 4, 열의 수가 3입니다. 행의 수가 더 많으므로 열의 수를 4로 만들기 위해 arr의 각 행의 끝에 0을 추가한 이차원 배열 [[572, 22, 37, 0], [287, 726, 384, 0], [85, 137, 292, 0], [487, 13, 876, 0]]를 return 합니다.

입출력 예 #2

• 예제 2번의 arr은 행의 수가 2, 열의 수가 4입니다. 열의 수가 더 많으므로 행의 수를 4로 만들기 위해 arr의 각 열의 끝에 0을 추가한 이차원 배열 [[57, 192, 534, 2], [9, 345, 192, 999], [0, 0, 0, 0], [0, 0, 0, 0]]을 return 합니다.

입출력 예 #3

• 예제 3번의 arr은 행의 수와 열의 수가 2로 같습니다. 따라서 0을 추가하지 않고 [[1, 2], [3, 4]]을 return 합니다.

solution.py

def solution(arr):

    m = len(arr)
    n = len(arr[0])
    
    if m > n:
        for i in range(m):
            arr[i].extend([0] * (m - n))
    
    elif n > m:
        for _ in range(n - m):
            arr.append([0] * n)
    
    return arr

---

이차원 배열 대각선 순회하기

문제 설명

2차원 정수 배열 board와 정수 k가 주어집니다.

i + j <= k를 만족하는 모든 (i, j)에 대한 board[i][j]의 합을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ board의 길이 ≤ 100
• 1 ≤ board[i]의 길이 ≤ 100
  • 1 ≤ board[i][j] ≤ 10,000
  • 모든 board[i]의 길이는 같습니다.
• 0 ≤ k < board의 길이 + board[i]의 길이

입출력 예

board	k	result
[[0, 1, 2],[1, 2, 3],[2, 3, 4],[3, 4, 5]]	2	8

입출력 예 설명

입출력 예 #1

• 입출력 예 #1의 board를 표로 나타내면 다음과 같습니다.

i \ j	0	1	2
0	0	1	2
1	1	2	3
2	2	3	4
3	3	4	5

• i + j가 2보다 작거나 같은 항들의 합은 0 + 1 + 2 + 1 + 2 + 2 = 8이므로 8을 return 합니다.

solution.py

def solution(board, k):
    m = len(board)
    n = len(board[0])
    answer = 0
    
    for i in range(m):
        for j in range(n):
            if i + j <= k:
                answer += board[i][j]
    
    return answer