[JAVA] 프로그래머스 LEVEL4: 행렬과 연산

 

프로그래머스

 

문제 설명

당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.

• ShiftRow
  • 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.)
  • ShiftRow의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다.
    • 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다.

• Rotate
  • 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다.
  • 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다.
  • 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀려난다는 것을 의미합니다. 즉, 다음 4개의 연산이 동시에 시행됩니다.
    • 첫 행에서 끝 열에 있는 원소를 제외한 첫 행의 모든 원소는 오른쪽으로 한 칸 이동합니다.
    • 끝 열에서 끝 행에 있는 원소를 제외한 끝 열의 모든 원소는 아래쪽으로 한 칸 이동합니다.
    • 끝 행에서 첫 열에 있는 원소를 제외한 끝 행의 모든 원소는 왼쪽으로 한 칸 이동합니다.
    • 첫 열에서 첫 행에 있는 원소를 제외한 첫 열의 모든 원소는 위쪽으로 한 칸 이동합니다.
  • Rotate의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 Rotate를 한 번 시행한 뒤의 행렬입니다.
    • 바깥쪽에 있는 값들이 시계 방향으로 한 칸씩 이동한 것을 확인할 수 있습니다.

당신은 행렬에 연산을 여러 번 시행하려고 합니다.
행렬의 초기 상태를 담고 있는 2차원 정수 배열 rc, 시행할 연산을 순서대로 담고 있는 문자열 배열 operations가 매개변수로 주어졌을 때, 연산을 차례대로 시행한 후의 행렬 상태를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
• rc[i][j] 는 i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
  • 1 ≤ rc[i][j] ≤ 1,000,000
• 1 ≤ operations의 길이 ≤ 100,000
  • operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.

정확성 테스트 케이스 제한 사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 1,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 1,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 10,000
• 1 ≤ operations의 길이 ≤ 100

 

---

제한사항을 보자

• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000 

행과 열의 곱이 십만이다 그래서 O(N²)으로 푼다면 백억이 나오므로 무조건 시간초과다 

그래서 배열을 이용해 이중 for문으로 데이터를 다 넣는 것만으로도 이건 시간초과란이야기다... 배열의 데이터삽입의 시간복잡도가 O(N)이라서.. 

그래서 데이터 삽입시 시간복잡도가 O(1)인 Queue의 Deque를 이용해 볼 것이다 

Deque
양쪽 끝에서 데이터 삽입/삭제가 가능한 큐

이문제를 해결하기 위해선 Deque의 메서드를 잘 알아둬야 한다

deque.addLast(); //뒤에서 데이터 추가
deque.addFirst(); //앞에서 데이터 추가
deque.pollLast(); //뒤에서 데이터 가져오기
deque.PollFirst(); //앞에서 데이터 가져오기

그림과 같이 rotate일 땐 deque를 left, mid <midqueue>, right 3개의 큐로 나눈 후 

1.left의 first값을 mid의 이중 queue의 first queue에서 first값으로 넣어준다

2. mid의 이중 queue의 first queue의 last값을 right의 first값으로 넣어준다

3.right의 last값을 mid의 이중 queue의 last queue에서 last값으로 넣어준다

4. mid의 이중 queue의 last queue의 first값을 left의 last값으로 넣어준다 

이러한 순서로 rotate연산을 한다 그럼 시간복잡도는 O(1)이다

그림으로 설명해 보자면

이런 식이다

 

shift는 위의 그림처럼 각각의 큐의 마지마값을 첫 번째 값으로 넣어주면 된다

이 로직을 코드로 바꿔주면 된다

---

import java.util.ArrayDeque;

public class PRO_CT_15 {
    public static int[][] solution(int[][] rc, String[] operations) {
        int[][] answer = new int[rc.length][rc[0].length];
        
        ArrayDeque<Integer> left = new ArrayDeque<>(); //left dequeue
        ArrayDeque<ArrayDeque<Integer>> mid = new ArrayDeque<>(); //mid dequeue
        ArrayDeque<Integer> right = new ArrayDeque<>(); //right dequeue

        //데이터 삽입
        for(int i=0;i<rc.length;i++){
            left.addLast(rc[i][0]);
            ArrayDeque<Integer> midQueue=new ArrayDeque<>(); //이중데큐를 만들어준다
            for(int j=1;j<rc[0].length-1;j++){
                midQueue.addLast(rc[i][j]);
            }
            mid.addLast(midQueue);
            right.addLast(rc[i][rc[i].length-1]);
        }

        //연산실행
        for(String opration: operations){
        	//Shift
            if("ShiftRow".equals(opration)){
                left.addFirst(left.pollLast());
                mid.addFirst(mid.pollLast());
                right.addFirst(right.pollLast());
	
            }else{
            //Rotate
                mid.peekFirst().addFirst(left.pollFirst());
                right.addFirst(mid.peekFirst().pollLast());
                mid.peekLast().addLast(right.pollLast());
                left.addLast(mid.peekLast().pollFirst());
            }
        }

        //배열로 변경
        for(int i=0;i<answer.length;i++){
            answer[i][0]=left.pollFirst();
            ArrayDeque<Integer> midqueue=mid.pollFirst();
            for(int j=1;j<answer[0].length-1;j++){
                answer[i][j]=midqueue.pollFirst();
            }
            answer[i][answer[i].length-1]=right.pollFirst();
        }

        return answer;
    }

    public static void main(String[] args) {
        int[][]rc = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        String[] operatoins = {"Rotate", "ShiftRow"};

        System.out.println(solution(rc,operatoins));
    }
}

rotate에서 mid.peekFirst() 이렇게 peek을 써주는 이유는 mid가 이중데큐이기 때문이다

레벨 4이었던 만큼... 겁나 어려웠다.. 갓희성...

처음부터 시간복잡도를 생각하고 풀어서 다 통과했댜 진짜 시간복잡도 겁나 중요한걸 맨날 깨닫는 거 같다..