[프로그래머스/Kotlin] 행렬 테두리 회전

문제 링크 -> https://programmers.co.kr/learn/courses/30/lessons/77485

코딩테스트 연습 - 행렬 테두리 회전하기

다음은 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입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

------------------------------------------------------------풀이------------------------------------------------------------------
처음에 어떻게 하는게 좋을까.. 한칸식 이동시키면 시간이 너무 많이 걸릴 것 같은데 하다가 생각이 하나 났습니다. 
1. 값이 없어지는 지점의 value를 다른 변수에 저장해놓는다. 
2. 총 2번의 반복문을 사용한다. 1번 반복문에서 맨 윗줄과 아랫줄, 2번 반복문에서 왼쪽줄과 오른쪽줄을 시계방향 회전

5*5행렬일 때 (2,2,4,4)로 값이 들어왔다면 시계방향으로 움직이는 값은 아래와 같다

왼쪽부터 처음 상태, 1회전상태, 2회전상태, 최종상태이다. 
1회전에서는 맨 윗줄과 아랫줄을 시계방향으로 한칸씩 이동( 값 옮기기x 이전 값으로 초기화)
2회전에서는 오른쪽과 왼쪽을 시계방향으로 한칸씩 이동( 값 옮기기x 이전값으로 초기화)
2회전 상태와 최종상태를 비교하면 중복되는 값을 볼 수 있다. 중복되는 값중 맞지 않는 값을 제거하면 

 

비어있는 부분에 원래 들어갔어야 하는 값은 17, 9인데 이 값의 처음 위치는 아래와 같다.

 

 

 

그러면 처음 상태에서 이 꼭지점 두곳의 값을 다른곳에 저장해놓고 반복문 2번으로 
값을 옮긴다음에 가야할 위치 꼭지점에서 시계방향으로 한칸 이동한 위치에 대입하면?

 

마지막 정리! (x1, y1, x2, y2)값이 들어왔을 때
1. (x1, y2), (x2,y1)의 값을 다른 곳에 저장
2. 2번의 반복문을 통해 시계방향으로 값을 이동 
3. (x1, y2)의 값은 (x1+1, y2)에 대입, (x2, y1)의 값은 (x2-1, y1)에 대입
4. 이동하는 틈틈히 가장 작은 값을 찾아준다!     끝!

class Solution {
    fun solution(rows: Int, columns: Int, queries: Array<IntArray>): IntArray {
        var answer = ArrayList<Int>()
        var R = Array(rows){ i->
            Array<Int>(columns) { j -> ((i)*columns)+(j+1) }
        }
          
        for(i in queries){
            var vt2=R[i[0]-1][i[3]-1]; var vt4=R[i[2]-1][i[1]-1];// (x1, y2), (x2,y1) 시계방향 이동후 사라지는 꼭지점 
            var min = Int.MAX_VALUE
            var count = 0
            if( vt2 < min ) min = vt2
            if( vt4 < min ) min = vt4
            
            while( count < i[3]-i[1]){ //윗줄 아래줄 시계방향
                if( R[i[0]-1][(i[3]-1)-(count+1)] < min ){ min = R[i[0]-1][(i[3]-1)-(count+1)]  }
                if( R[i[2]-1][i[1]+count] < min ){ min = R[i[2]-1][i[1]+count] }
                
                R[i[0]-1][(i[3]-1)-count] = R[i[0]-1][(i[3]-1)-(count+1)]
                R[i[2]-1][(i[1]-1)+count] = R[i[2]-1][i[1]+count]
                count++
            }
            count = 0
          
            while(count < i[2]-i[0]){ //왼쪽 오른쪽 줄 시계방향 이동
                if( R[(i[0]-1)+(count+1)][i[1]-1]< min ){ min = R[(i[0]-1)+(count+1)][i[1]-1] }
                if( R[(i[2]-1)-(count+1)][i[3]-1]< min ){ min = R[(i[2]-1)-(count+1)][i[3]-1] }
                
                R[(i[0]-1)+count][i[1]-1] = R[(i[0]-1)+(count+1)][i[1]-1]
                R[(i[2]-1)-count][i[3]-1] = R[(i[2]-1)-(count+1)][i[3]-1]
                count++
            }
           
            R[i[0]][i[3]-1] = vt2 //빈 부분 대입
            R[i[2]-2][i[1]-1] = vt4 // 빈 부분 대입
            answer.add(min)
        }
        return answer.toIntArray()
    }
}

2차원 행렬을 사용해서 코드가 조금 복잡하지만, 이해하신다면 개인 스타일로 쉽게 작성할 수 있습니다.------------------------------------------------------------결과------------------------------------------------------------------

더 좋은 풀이법을 알고 계신분은 알려주세요! 참고해서 수정하겠습니다!

 

 

 

 

 

- 문제에 대한 질문 댓글 환영!
- 중간에 잘못된 부분이 있다면 댓글로 남겨주세요. 수정하겠습니다.