Problem Solving
간만에 알고리즘 문제풀이를 한다.
오늘 푼 문제는 Rotate Image다.
사실 코딩테스트가 입사 시험에서 대중화 되면서, 그 중에서도 구현 관련된 많은 솔루션들이 있고 대게는 그러한 방식을 많이 따라하게 된다.
이제부터 보려하는 Rotate Image는 약간 이런 틀을 깨는 문제라고 생각을 한다.
대부분의 사람들은 2차원 배열을 시계, 반시계 방향으로 회전 할때 새로운 2차원 배열을 보통은 하나 더 선언한다.
왜냐하면 이유는 간단하다. 대게는 메모리가 부족할 상황이 오지않고, 제약이 딱히 존재하지 않기 때문이다.
그런 상황에서는 다음과 같이 코드를 짜볼수 있다.
//정사각형
let range = 0..<oneSideLength
//시계방향
for i in range {
for j in range {
newMap[i][j] = oldMap[j][oneSideLength - 1 - i]
}
}
//반 시계방향
for i in range {
for j in range {
newMap[i][j] = oldMap[oneSideLength - 1 -j][i]
}
}
그러나 Rotate Image는 문제풀이 입장부터 보면 심상치가 않다
새로운 2차원 배열을 선언하지 말라는 뜻이다.
그럼 이때부터 살짝 망설여지고 당장 떠오르는것은 몇개 없을 것이다.
나는 처음에 문제를 보고 생각한것은 사실 제약사항이 크지않길래 한땀한땀 최대 변 길이 수만큼 다옮겨주면 되지 않나!!! 라는 무식한 생각을 했다.
그런데 조금 생각을 해보니 나오는 결론은 로테이션이 필요한 사각형의 맨 윗 변들만 돌아야 하는 만큼 돌면 된다는 것이다.
예를들어 5 x 5 배열을 하나 생각해보자.
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY이런 배열이 있다고 했을때,
가장 외곽을 둘러 쌓은 사각형의 가장 윗변인 ABCDE를 보자.
제일 우선적으로 A가 시계방향으로 이동했을때 들어갈곳은 바로 E다.
가장 먼저 E를 보관하고 그 자리에 A를 넣는다고 하자.
0BCDA
FGHIJ
KLMNO
PQRST
UVWXY 보관함 : E와 같이 행렬을 바꿀수 있고 이번에는 보관했던 E를 다음차례인 Y에 넣어야하는데
마찬가지로, Y도 보관을 한뒤에 그자리에 보관했던 E를 넣자.
0BCDA
FGHIJ
KLMNO
PQRST
UVWXE 보관함 : Y그러면 다음과 같은 방식으로 두번 더하게 되면..
0BCDA UBCDA
FGHIJ FGHIJ
KLMNO ->KLMNO
PQRST PQRST
YVWXE YVWXE이런 식으로 각 변들의 위치가 바뀌게 된다.
이것을 이제 남은 BCD에도 적용할수있게 된다.
즉, 이러한 과정 도출을 통해 외곽의 사각형들의 윗변을 이러한 방식으로 로테이션 시키면
원하는 로테이션을 추가 행렬 없이도 구현할수 있다는 점을 알수 있다.
그래서, 오늘 보고자 했던 문제의 풀이는 다음과 같다.
class Solution {
func rotate(_ matrix: inout [[Int]]) {
let len = matrix.count
for i in 0..<(len / 2){
for j in i..<(len - 1 - i) {
var x = j
var y = len - 1 - i
var temp = matrix[j][len - 1 - i]
matrix[j][len - 1 - i] = matrix[i][j]
var temp2 = matrix[y][len - 1 - x]
matrix[y][len - 1 - x] = temp
let tp = x
x = y
y = len - 1 - tp
temp = matrix[y][len - 1 - x]
matrix[y][len - 1 - x] = temp2
matrix[i][j] = temp
}
}
}
}
굉장히 간단하게 풀수 있다. 배열도 다 돌필요 없이, 외곽의 윗변들만 잘 처리하자.
