rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요. 행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중가장 작은 숫자들을 순서대로 배열에 담아return 하도록 solution 함수를 완성해주세요.
2. 문제의 조건
2 <= rows <= 100
2 <= columns <= 100
queries는 [x1, y1, x2, y2]로 표현하는데 이는 행, 열, 행, 열을 나타내는 것이다. 행 = y축을 나타내며 열은 x축을 나타내는데 문제는 이를 헷갈리게 적어놓았으므로 주의하여햐한다.
주어진 행렬의 크기를 탐색할 수 있는가.. 즉, 구현력의 문제입니다. x1, y1이 주어진다면 (x, y) 기준으로 (y1, x1)이 되는 것입니다. (항상 주의 행 : y, 열 : x 축이기 떄문) 그리고 탐색 범위는 y_bar = x2 - x1, x_bar = y2- y1이 기준이됩니다. (2, 2)에서 (5, 4)을 탐색한다면 (0, 0) 기준으로 x축은 3칸 y축은 2칸을 가야하기 떄문입니다. 그렇게 되면 현재 지점 pos_y, pos_x 에서 x_bar와 y_bar만큼 가면 됩니다. 또한 탐색은 현재 위치 pos_x, pos_y 부터 오른쪽 아래 왼쪽 위 순으로 탐색하였을 때 이동 범위를 먼저 파악해야합니다. 이동 범위는 (x_bar, y_bar, x_bar, y_bar - 1) 만큼 이동하면 됩니다.
또한 이동한 후의 값을 과거로 바꾸면 현재의 값을 미래로 바꾸어야합니다. 즉, 0 1 2 [1, 2, 3] 이면 현재 1의 값을 1로 바꾸면 바꾸기전의 2라는 값은 다음으로 가야하므로 미리 기억을 해야합니다. 그리고 바뀐 최소값을 항상 기억해야합니다.
4. 풀이 방법
1부터 n*n인 2차원 배열을 생성합니다.
모든 queries를 idx가 0을 기준으로 시작하게 1을 빼줍니다.
현재 위치와 가야할 위치 범위를 기억합니다.
오른쪽, 아래, 왼쪽, 위 순서로 각 주어진 위치 범위 만큼 이동합니다. 이때, 첫시작인지 파악하여 미래의 값을 잃지 않게 저장해주어야 합니다.
현재의 값이 최소값인지 항상 갱신을하며 최소이면 result에 넣어줍니다.
끝나면 마지막으로 한번 더 최소인지 비교를 해주고 (pos_x, pos_y)을 비교 값을 추가합니다.
댓글