이차원 배열 회전시키는 방법
1. 문제
https://programmers.co.kr/learn/courses/30/lessons/77485
코딩테스트 연습 - 행렬 테두리 회전하기
6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3]
programmers.co.kr
rows * columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows * columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다.
이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다.
각 회전은 (x1,y1,x2,y2)인 정수 4개로 표현하며 그 의미는 다음과 같습니다.
x1행 y1열부터 x2행 y2열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6*6 크기 행렬의 예시입니다.
이 행렬에 (2,2,5,4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다.
이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤,
그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return하도록 solution함수를 완성하세요.
2. 제한사항
rows는 2이상 100이하인 자연수
columns는 2이상 100이하인 자연수
처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
즉 아무 회전도 하지 않았을 때, i행 j열에 있는 숫자는 ((i-1)*columns+j)입니다.
queries의 행의 개수(회전의 개수)는 1이상 10000이하
queries의 각 행은 4개의 정수 [x1,y1,x2,y2]입니다.
x1행 y1열부터 x2행 y2열까지의 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
모든 회전은 순서대로 이어집니다.
예를 들어 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때, 이동한 숫자 중 최솟값을 구하면 됩니다.
1<= x1 < x2 <= rows, 1<= y1 < y2 <= columns입니다.
3. 입출력 예시
4. 예시 설명
예시 3에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.
5. 나의 풀이
일단 먼저 rows*columns의 사각형 배열을 만들고 1부터 rows*column까지 숫자를 채워넣어야할 것 같다.
그런데 그 숫자의 위치를 특정할 수 있을까??
임의의 (m,n) 위치에 있는 값이 무엇인지 알 수 있을까?
파이썬은 0부터 시작하니까 이걸 따라서
m번째 row에 있는 숫자라면 m*columns + n 이 될 것이다.
예를 들어 (2,2)에 있는 15는 어떻게 구할까
m * columns + n에서 m=2, columns=6, n=2로 구해졌다.
def solution(rows,columns,queries):
from collections import deque
answer = []
answer_list = []
square = [[c for c in range(columns*r+1,columns*r+1+columns)] for r in range(rows)]
[[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12], [13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24], [25, 26, 27, 28, 29, 30], [31, 32, 33, 34, 35, 36]]
행의 위치를 r로 특정하여 0부터 rows-1까지 세고 m*columns+n을 이용하여 r행의 첫 숫자 n=1이고 마지막 숫자는 n=columns잖아
columns*r+1부터 columns*r+columns까지 가야하니까 마지막은 columns*r+columns+1로 해줘야지
다음 회전을 어떻게 시킬지 생각을 해봤는데 4가지 부분으로 나눌 수 있단말이지
x1,y1,x2,y2가 1부터 시작한다고 제한사항에 나와있기 때문에 파이썬의 zero index로 바꿔서 생각해서
위와 같이 x1-1행 y1-1열부터 x2-1행 y1-1열까지를 첫번째 부분
x1-1행의 y1-1열부터 y2-1열까지를 두번째 부분, x1-1행 y2-1열부터 x2-1행 y2-1열까지를 세번째 부분
x2-1행의 y2-1열부터 y1-1열까지를 네번째 부분으로 생각해서 각각을 리스트로 만들면 4가지 부분이 결국 회전하는 영역
그 4가지 리스트 각각에서 최솟값을 뽑고 이들중에서 최솟값이 현재 회전에서 최솟값이 될거
def solution(rows,columns,queries):
from collections import deque
answer = []
answer_list = []
square = [[c for c in range(columns*r+1,columns*r+1+columns)] for r in range(rows)]
for x1,y1,x2,y2 in queries:
list_one = list(list(zip(*square))[y1-1][x1-1:x2])
answer_list.append(min(list_one))
list_two = square[x1-1][y1-1:y2]
answer_list.append(min(list_two))
list_three = list(list(zip(*square))[y2-1][x1-1:x2])
answer_list.append(min(list_three))
list_four = square[x2-1][y1-1:y2]
answer_list.append(min(list_four))
answer.append(min(answer_list))
먼저 y1-1열을 가져오기 위해 list(zip(*square))를 이용했다.
예를 들어서 square가
[[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12], [13, 14, 15, 16, 17, 18], [19, 20, 21, 22, 23, 24], [25, 26, 27, 28, 29, 30], [31, 32, 33, 34, 35, 36]] 이니까 *square를 하면
[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12], [13, 14, 15, 16, 17, 18], [19, 20, 21, 22, 23, 24], [25, 26, 27, 28, 29, 30], [31, 32, 33, 34, 35, 36] 6개의 리스트를 zip으로 묶는데
이걸 list()로 씌우면 [(1, 7, 13, 19, 25, 31), (2, 8, 14, 20, 26, 32), (3, 9, 15, 21, 27, 33), (4, 10, 16, 22, 28, 34), (5, 11, 17, 23, 29, 35), (6, 12, 18, 24, 30, 36)] 이 된다.
배열의 열을 리스트로 가져온다
그러면 list(zip(*square))[y1-1]하면 y1-1열을 가져올것인데 위에서는 예를 들어 y1=2인 1열 (2,8,14,20,26,32)인 tuple을 가져온다.
여기서 x1-1행부터 x2-1행까지를 가져와야해서 list(zip(*square))[y1-1][x1-1:x2]로 슬라이싱을 한다.
예를 들어 1행부터 4행까지 가져오니까 (8,14,20,26)이 될것이다.
그런데 tuple은 원소변경이 안되니까 다시한번 list()로 씌워준다
list(list(zip(*square))[y1-1][x1-1:x2]) 이렇게 완성된 것이 list_one이고 여기서 최솟값을 answer_list에 넣어준다.
이런 원리로 세번째 부분 list_three도 만들어졌다.
list_two를 보면 square가 행들의 리스트여서 x1-1행은 square[x1-1]로 쉽게 가져올 수 있고 여기에 y1-1열부터 y2-1열을 가져와야하니까 square[x1-1][y1-1:y2]로 가져온다.
여기서 최솟값을 answer_list에 넣어주고 list_four도 동일한 원리로 만들어졌다.
문제는 list_one,two,three,four에 중복되는 값이 있는데 최솟값 넣어도 되는거 맞냐???
어차피 answer_list에 들어간 4개의 값중 최솟값을 answer에 넣을거니까 상관없다
예를 들어서 위와 같은 경우는 answer_list에 [4,1,1,2]가 들어가는데 여기서 최솟값은 1이고 실제로 저 4개의 수 4,1,5,2중 최솟값은 1로 잘 찾는다
그런데 다음 문제가 실제로 회전을 시켜서 square를 변형시켜야하는데 이게 문제다.
def solution(rows,columns,queries):
from collections import deque
answer = []
answer_list = []
square = [[c for c in range(columns*r+1,columns*r+1+columns)] for r in range(rows)]
for x1,y1,x2,y2 in queries:
list_one = list(list(zip(*square))[y1-1][x1-1:x2])
answer_list.append(min(list_one))
list_two = square[x1-1][y1-1:y2]
answer_list.append(min(list_two))
list_three = list(list(zip(*square))[y2-1][x1-1:x2])
answer_list.append(min(list_three))
list_four = square[x2-1][y1-1:y2]
answer_list.append(min(list_four))
answer.append(min(answer_list))
####
list_one = list_one[1:]
list_two[1:] = list_two
list_two[0] = list_one[0]
list_two.pop(-1)
list_three[1:] = list_three
list_three[0] = list_two[-1]
list_three.pop(-1)
list_four = list_four[1:]
list_four.append(list_three[-1])
list_one.append(list_four[0])
square[x1-1][y1-1:y2] = list_two
i = 0
for a,b in zip(list_one,list_three):
square[x1-1+i][y1-1] = a
square[x1-1+i][y2-1] = b
i += 1
square[x2-1][y1-1:y2] = list_four
return answer
그림을 보면서 생각을 해보자고
첫번째 부분의 리스트 [8,14,20,26]에서 1번원소부터 가져온 [14,20,26]을 list_one으로 하고
-------------------------------------------------------------------------------------------------------------
list_two = [8,9,10]인데 list_two[1:] = list_two를 하면 어떻게 될까
a[1:]가 [9,10]을 담고있는 변수가 아니라는 점에 주목하자.
a[1:]는 단순히 a라는 변수에서 [9,10]까지를 지정한 것 뿐이고 여기에 [8,9,10]을 위 그림처럼 그대로 집어넣은거다.
그러니까 [8,9,10]에서 9,10부분에 [8,9,10]을 그대로 넣으니까 [8,8,9,10]이 된다.
-------------------------------------------------------------------------------------------------------------
아무튼 list_two = [8,8,9,10]이고 여기서 0번째 원소 8을 list_one = [14,20,26]에서 첫번째 원소인 14로 대체한다.
시계방향으로 움직이면 14가 8자리로 들어갈거고 8은 9자리로 들어갈거니까
그러면 list_two = [14,8,9,10]인데 list_two.pop(-1)로 마지막 원소 10을 제거하여 [14,8,9]로 변경시키면 된다.
list_three도 비슷한 방식으로 list_three = [10,16,22,28]인데 list_three[1:] = list_three를 하면
[10,10,16,22,28]이 될거고 숫자 9가 10의 위치로 가야하는데 현재 list_two = [14,8,9]니까 list_two의 마지막 원소
9가 list_three의 첫번째 원소로 가야하니까 list_three[0] = list_two[-1]이다.
그러면 list_three = [9,10,16,22,28]인데 마지막 28은 옮겨져야하니까 list_three.pop(-1)로 제거함
그러면 list_four = [26,27,28]인데 첫번째 원소부터만 가져와서 list_four = [27,28]이고 list_three = [9,10,16,22]에서 마지막 원소 22가 list_four로 가야하니까
list_four.append(list_three[-1])을 해준다. 그러면 list_four = [27,28,22]이고 현재 list_one = [14,20,26]인데
27이 26 자리로 들어가야하니까 list_four의 첫번째 원소를 list_one에 넣어준다면
list_one = [14,20,26,27]이 될것이다
그러면 list_one = [14,20,26,27] , list_two = [14,8,9], list_three = [9,10,16,22], list_four = [27,28,22]이다.
그러면 이들을 square에 덮어씌워주자
square[x1-1][y1-1:y2] = list_two
i= 0
for a,b in zip(list_one,list_three):
square[x1-1+i][y1-1] = a
square[x1-1+i][y2-1] = b
i += 1
square[x2-1][y1-1:y2] = list_four
x1-1행부터 y1-1열부터 y2-1열까지는 list_two로 씌우고
x2-1행부터 y1-1열부터 y2-1열까지는 list_four로 씌우고
첫번째 부분과 세번째 부분은 list_one과 list_three를 zip으로 묶어서 for문을 돌건데
i=0부터 시작하고 y1-1열은 첫번째 부분이니까 a를 넣을거고 y2-1은 세번째 부분이니까 b를 넣으면 되는데
x1-1행부터 x2-1행까지 돌거잖어 그래서 x1-1+i행 y1-1열, y2-1열에 각각 a,b를 넣고 i=0부터 i를 1씩 증가시키면 되겠지
그러면 시계방향으로 회전시킨 square를 얻는데까지 성공한다.
6. 다른 풀이
좋아요를 가장 많이 받은 풀이를 분석해본다면
def solution(rows, columns, queries):
answer = []
board = [[i+(j)*columns for i in range(1,columns+1)] for j in range(rows)]
# print(board)
for a,b,c,d in queries:
stack = []
r1, c1, r2, c2 = a-1, b-1, c-1, d-1
for i in range(c1, c2+1):
stack.append(board[r1][i])
if len(stack) == 1:
continue
else:
board[r1][i] = stack[-2]
for j in range(r1+1, r2+1):
stack.append(board[j][i])
board[j][i] = stack[-2]
for k in range(c2-1, c1-1, -1):
stack.append(board[j][k])
board[j][k] = stack[-2]
for l in range(r2-1, r1-1, -1):
stack.append(board[l][k])
board[l][k] = stack[-2]
answer.append(min(stack))
return answer
square를 만들듯이 시작 board를 만들고 queries에서 a,b,c,d를 뽑아 각각 1씩 빼서 파이썬 index로 바꾼게 r1,c1,r2,c2네
stack=[]으로 초기화했는데
첫번째 for문은 나의 두번째 부분 인 r1행에서 c1열~c2열까지를 순회한것인데
예를 들어서 [8,9,10]이란 말이지
여기를 stack에 하나씩 쌓아
근데 stack의 길이가 1이면 for문을 넘어가고 1이 아니라면 먼저 집어넣은 stack[-2]를 board[r1][i]에 변경시키는데?
i=0이면 stack = [8]이고 길이가 1이니까 넘어가
i=1이면 stack = [8,9]이고 길이가 1이 아니니까 board[r1][1]은 현재 9인데 stack[-2] = 8을 집어넣어
i=2이면 stack = [8,9,10]이고 길이가 1이 아니니까 board[r1][2]는 현재 10인데 stack[-2] = 9를 집어넣어서
그러면 현재 square는 위와 같겠지??? 두번쨰 for문은 나의 세번째 부분인 [10,16,22,28]이다
for i in range(c1, c2+1):
stack.append(board[r1][i])
if len(stack) == 1:
continue
else:
board[r1][i] = stack[-2]
for j in range(r1+1, r2+1):
stack.append(board[j][i])
board[j][i] = stack[-2]
j를 r1+1부터 r2까지 순회한다... r1부터가 아니라 r1+1부터 순회한다는게 멋지네
[10,16,22,28]을 건드는게 아니라 [16,22,28]을 건들고 있다
그리고 이전에 사용한 i를 그대로 가져온다.. 그러니까 현재 c2열로 고정되어있다
stack = [8,9,10]이고 j=r1+1이면 16을 stack에 넣고 stack=[8,9,10,16]인데 stack[-2]=10을 16자리에 넣고...
stack = [8,9,10,16]에서 j=r1+2이면 22를 stack에 넣고 stack = [8,9,10,16,22]인데 stack[-2] = 16을 22자리에 넣고...
그러면 최종적으로 stack = [8,9,10,16,22,28]이고...
현재 board는 위와 같겠지.. 세번째 for문을 돌면
for j in range(r1+1, r2+1):
stack.append(board[j][i])
board[j][i] = stack[-2]
for k in range(c2-1, c1-1, -1):
stack.append(board[j][k])
board[j][k] = stack[-2]
현재 j = r2이고.. 그래서 r2행으로 현재 고정된 상태
k를 c2-1부터 c1까지 역으로 돌거니까 range(c2-1,c1-1,-1)로 했네... 이것도 멋지다
그러면 현재 stack = [8,9,10,16,22,28]이고... c2열부터가 아니고 c2-1열부터 건들거라서 [27,26]을 차례대로 건들건데
27을 stack에 넣어서 [8,9,10,16,22,28,27]이고 stack[-2] = 28은 27자리에 넣고..
26을 stack에 넣어서 [8,9,10,16,22,28,27,26]이고 stack[-2] = 27은 26자리에 넣는다..
세번쨰 for문까지 돌면 현재 board는 위와 같고.. 네번째 for문을 돌면
for k in range(c2-1, c1-1, -1):
stack.append(board[j][k])
board[j][k] = stack[-2]
for l in range(r2-1, r1-1, -1):
stack.append(board[l][k])
board[l][k] = stack[-2]
이전의 k = c1으로 현재 c1열이 고정된 상태이고.. l=r2-1부터 r1까지 역으로 돌기 위해 range(r2-1,r1-1,-1)을 사용했고
현재 stack = [8,9,10,16,22,28,27,26]이고 그래서 [20,14]를 차례대로 건들여서...
stack = [8,9,10,16,22,28,27,26,20,14]가 될거고.. 이것은 놀랍게도 정확히 시계방향으로 회전하는 부분의 원소들만 가져온 셈이다
그래서 여기의 min을 answer에 집어넣으면 되겠지
그리고 stack이 완성되면서 board도 놀랍게도 변형이 끝났네???
곱씹어보니까 이건 좀 대단하긴하네
7. 되돌아보기
억지로 코딩한 감이 없지않아 있지만 맞춘건 분명 대단한거다
list[1:] = list의 원리를 잘 기억하자
list[1:]는 변수가 아니야
list에서 1번부터 끝까지 위치를 지정했고 여기에 list를 그대로 덮어씌우거든
그러니까 [1,2,3]이면 [1,1,2,3]이 된다는 소리
그리고 다른 풀이에서 for문을 연결시켜서 사용했고...
그냥 자연스럽게 시계방향으로 회전하는 부분을 하나하나 순회한거
순회하면서 stack에 쌓아넣고 이를 이용해서 board의 원소를 자연스럽게 변경시키는
역으로 순회할때는? range(r2-1,r1-1,-1)로.. 마지막 step=-1로 둔다면 좋고
'알고리즘 > 알고리즘 일반' 카테고리의 다른 글
| 2진수 변환을 가장 빠르게 하는 방법 (0) | 2022.05.19 |
|---|---|
| 사각맵에서 가장 빨리 목적지로 도달하는 최단 경로 찾는 방법 (0) | 2022.05.03 |
| 중복을 허용하는 집합 다루기 (0) | 2022.04.17 |
| 진수 변환 알고리즘 활용하기 (0) | 2022.04.16 |
| 파이썬 문자열 필수 스킬 - N-gram 순회하기, 대소문자를 무시한 변환 (0) | 2022.04.10 |
