문제 설명
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 함수를 완성해주세요.
제한 사항
- rows는 2 이상 100 이하인 자연수입니다.
- columns는 2 이상 100 이하인 자연수입니다.
- 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
- 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
- queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
- queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
- x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
- 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
- 모든 회전은 순서대로 이루어집니다.
- 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
입출력 예시
| rows | columns | queries | result |
|---|---|---|---|
| 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] |
| 100 | 97 | [[1,1,100,97]] | [1] |
입출력 예 설명
입출력 예 #1
-
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
-
입출력 예 #2
-
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
-
입출력 예 #3
- 이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.
내가 제출한 코드
import Foundation
let MAX_MATRIX_VALUE: Int = 10001
func solution(_ rows:Int, _ columns:Int, _ queries:[[Int]]) -> [Int] {
var minArray: [Int] = [] // 회전한 값들 중 최솟값
var matrixArray = makeMatrix(rows, columns) // rows * column 행렬 만듬
for query in queries { // 회전 수행
minArray.append(rotateMatrix(&matrixArray,query))
}
return minArray
}
func rotateMatrix(_ matrixArray: inout [[Int]], _ rotateRange: [Int]) -> Int {
var minValue: Int = MAX_MATRIX_VALUE // 회전한 값중 최솟값
let x1:Int = rotateRange[0] - 1, y1 = rotateRange[1] - 1
let x2:Int = rotateRange[2] - 1, y2 = rotateRange[3] - 1
let row: Int = rotateRange[2] - rotateRange[0] + 1 // 회전할 직사각형 영역의 세로
let column: Int = rotateRange[3] - rotateRange[1] + 1 // 회전할 직사각형 영역의 가로
let rotateRectangle = matrixArray[x1...x2].map{Array($0[y1...y2])} // 회전할 영역의 숫자들을 뽑음
// 4가지 방향으로 회전
for i in 0..<row {
for j in 0..<column { // 3
if i == 0 && j != 0 { // -> 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i][j-1]
} else if i != 0 && j == column - 1 { // 아래방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i-1][j]
} else if i == row - 1 && j != column - 1 { // <- 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i][j+1]
} else if i != row - 1 && j == 0 { // 위로 올라가는 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i+1][j]
}
}
}
return minValue
}
// rows * column 행렬 만듬
func makeMatrix(_ rows: Int, _ columns: Int) -> [[Int]]{
var martrix: [[Int]] = []
for i in 1...rows {
var tmp: [Int] = []
for j in 1...columns {
tmp.append((i-1)*columns + j)
}
martrix.append(tmp)
}
return martrix
}코드 설명
이번 문제는 2차원 행렬을 회전하는 문제이다. 우리가 집중적으로 구현해야 할 부분은 회전할 직사각형 영역에 접근, 접근한 영역의 회전이다. 영역의 회전에는 여러 가지 방법이 있다. 다른 풀이에서는 4개의 테두리 영역을 4번의 반복문을 걸쳐 회전하는 방법을 사용하나, 본 글은 직사각형의 영역을 얻은 후 해당 영역을 테두리로 접근하는 것이 아닌 1칸씩 접근하는 방법을 사용한다.
그러면 코드를 설명한다.
우선 rows * columns 행렬을 만드는 함수 makeMatrix이다.
// rows * column 행렬 만듬
func makeMatrix(_ rows: Int, _ columns: Int) -> [[Int]]{
var martrix: [[Int]] = []
for i in 1...rows {
var tmp: [Int] = []
for j in 1...columns {
tmp.append((i-1)*columns + j)
}
martrix.append(tmp)
}
return martrix
}우리가 만들 행렬이 2차원 행렬이므로, 2차원 배열을 만든다. 행렬에 들어갈 값은 왼쪽에서 오른쪽으로 1부터 1씩 증가한다.
행렬을 만들었다면 정해진 영역만큼 회전을 해야한다. 아래 코드는 회전을 수행하는 함수 rotateMatrix이다.
func rotateMatrix(_ matrixArray: inout [[Int]], _ rotateRange: [Int]) -> Int {
var minValue: Int = MAX_MATRIX_VALUE // 회전한 값중 최솟값
let x1:Int = rotateRange[0] - 1, y1 = rotateRange[1] - 1
let x2:Int = rotateRange[2] - 1, y2 = rotateRange[3] - 1
let row: Int = rotateRange[2] - rotateRange[0] + 1 // 회전할 직사각형 영역의 세로
let column: Int = rotateRange[3] - rotateRange[1] + 1 // 회전할 직사각형 영역의 가로
let rotateRectangle = matrixArray[x1...x2].map{Array($0[y1...y2])} // 회전할 영역의 숫자들을 뽑음
// 4가지 방향으로 회전
for i in 0..<row {
for j in 0..<column { // 3
if i == 0 && j != 0 { // -> 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i][j-1]
} else if i != 0 && j == column - 1 { // 아래방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i-1][j]
} else if i == row - 1 && j != column - 1 { // <- 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i][j+1]
} else if i != row - 1 && j == 0 { // 위로 올라가는 방향
minValue = min(minValue, rotateRectangle[i][j])
matrixArray[i+x1][j+y1] = rotateRectangle[i+1][j]
}
}
}
return minValue
}minValue프로퍼티는 회전하는 값들 중 최솟값을 저장한다. 초깃값은 10001로 할당한다. 열과 행이 최대 100의 크기를 가지므로 행렬이 가질 수 있는 최댓값이 10000이기 때문이다. row와 column은 회전할 직사각형의 세로와 가로를 나타낸다.
다음으로 우리는 행렬에서 회전할 영역의 직사각형을 얻어야 한다. 방법은 서브스크립트(Subscript)를 사용한다. 서브스크립트의 파라미터의 값은 Range<Int>타입이다. 우리는 이 서브스크립트를 보통 1차원 배열에서 주로 사용했다. 그러나 코드에서는 2차원 배열에서 사용된다. 2차원 배열 서브스크립트에 관한 설명은 제일 하단에 설명하니 참고하길 바란다. 얻은 직사각형 영역을 rotateRectangle 프로퍼티에 할당한다. 마찬가지로 이 프로퍼티도 2차원 배열이다.
이제 행렬을 회전해야 한다. 회전으로 rotateRectangle프로퍼티의 값이 바뀌는 것이 아닌, 우리가 이전에 만든 matrixArray 2차원 행렬이 회전하며 값이 변경된다. 그러면 직사각형 영역은 왜 구했을까?
이유는 회전을 쉽게 하기 위해서다. 만약 행렬의 영역을 복사하지 않고 회전한다고 가정하자.
우리는 위 그림의 행렬에서 (2,2,5,4)회전을 적용할 것이다. 그러면 값 (2,2)의 위치의 값은 14 가된다. 그러나 이전의 값 8은 (2,3)의 위치로 옮겨야 하기 때문에 (2,2)을 바꾸기 전에 해당 위치의 값을 가지고 있어야 한다. 즉 (2,2) -> (2,3) -> (2,4) -> (3,4)... -> (3,2)의 방향으로 회전을 하면서 동시에 이전의 값을 저장해야 한다. 이를 코드로 구현하는 것은 매우 복잡할 것이다. 그래서 우리는 직사각형의 영역을 따로 뽑아내어 회전에 적용시킨다.
적용 방법은 직사각형의 영역만큼 반복문을 순회하면서 복사한 직사각형 영역을 참조하여 값을 바꾸는 것이다. 다시 말해 원래 행렬에서 회전할 값을 직사각형 영역에서 찾으면 된다. 그러면 우리는 어떻게 2개의 2차원 배열을 매칭해야 할까? 바로 직사각형 영역의 열과 행을 0부터 끝까지 반복하면서, 기존의 2차원 행렬 인덱스에는 x1, y1을 각각 더해주면 된다. 더해주는 이유는 자른 직사각형의 영역이 0부터 시작하기 때문이다. 혹시나 이해가 가지 않는다면 댓글을 남겨주세요.
그런데 회전 방향은 4가지 방향이다. 각 방향마다 인덱스의 값이 다르므로 4가지의 조건문을 사용하여 판별한다. 회전을 하면서 회전하는 값들 중 최솟값을 찾기 위해 min(:)함수를 사용하여 최솟값을 업데이트한다. 반복문의 순회가 끝나면 minValue 프로퍼티에는 최솟값이 저장되어 있다. 이를 매 query마다 반복하면 우리가 원하는 해답을 얻을 수 있다.
코드 리뷰
나는 행렬을 회전하는 방법으로 1개의 반복문으로 직사각형의 영역의 넓이를 전부 순회하면서 조건문을 이용하여 모든 테두리를 판별하고 회전하였다. 그러나 대부분의 다른 사람들은 1개의 반복문이 아닌 4개의 반복문을 사용하여 각 반복문마다 1개의 테두리에 접근한다.
2가지 방법의 차이는 중앙에 있는 값의 참조 여부이다. 내 방법으로 순회하면 중앙 영역 모두 방문한다. 그러나 반복문을 4번 사용하면 직사각형의 테두리만 접근하기 때문에 실제로 회전하지 않는 중앙 영역을 참조하지 않는다. 이는 탐색 횟수에서 차이가 난다.
그렇기 때문에 시간적인 측면에서 테두리로 접근하는 방법이 더 효율적이다. 그래서 다음부터는 이런 유형의 문제를 만나면 테두리로 접근하는 방법을 사용해야겠다.
몰랐던 사실 or 기억하면 도움이 될 만한 사실
Swift 2차원 배열 slice
이번 문제에서 처음으로 2차원 배열의 slice을 사용하였다. Swift에서는 서브스크립트 개념이 있어 배열을 슬라이스할 때 Range<Int>타입을 사용한다. 나는 파이썬을 사용하면서 2차원 배열을 슬라이스 한 경험이 있어 같은 방법으로 처음에 접근하였다.
그러나 결과는 명확히 달랐다.
let towDimensionArray: [[Int]] = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12]]
print(towDimensionArray[1..<2][1..<2])
// Prints [[5, 6, 7, 8]]내가 원하는 것은 2차원 배열의 1행에서 1열의 값을 얻는 것이다. 그러나 위는 2차원 배열의 1행 자체를 반환한다. 위를 이해하기 위해 관련 검색을 하였으나 공식 문서나 관련 자료가 없어 위 방식이 어떻게 작동하는지 알지 못하였다. 만약 알고 있는 분이 있다면 알려주면 감사합니다..
그러면 2차원 배열의 slice는 어떻게 해야 할까? 아래 코드를 보자.
let towDimensionArray: [[Int]] = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12]]
print(towDimensionArray[1..<2].map{$0[1...2]})
// Prints [ArraySlice([6, 7])]towDimensionArray 배열에서 우선 첫 서브스크립트로 행을 접근한다. 위 예제에서는 1행을 접근할 것이다. 슬라이스 한 배열의 인스턴스 메소드 map을 호출하여 슬라이스 된 배열(1행)의 [1...2] 만큼(1열과 2열) 슬라이스하고 결과를 반환한다. 그러면 towDimensionArray 배열의 1행의 1열과 2열의 값을 2차원 배열로 얻을 수 있다.
만약 2차원 배열로 접근하면 위 방법을 이용하도록 하자.
