[프로그래머스/Programmers] 행렬과 연산 (Java - Queue - Level4)

프로그래머스

---

⭐️ 코드

import java.util.ArrayDeque;

public int[][] solution(int[][] rc, String[] operations) {

    int[][] answer = new int[rc.length][rc[0].length];

    ArrayDeque<Integer> left = new ArrayDeque<>(); // 좌측 열
    ArrayDeque<Integer> right = new ArrayDeque<>(); // 우측 열
    ArrayDeque<ArrayDeque<Integer>> mid = new ArrayDeque<>(); // 가운데 n열

    // 초기 값 Queue에 입력
    // O(N) -> N = rows * cols <= 100,000
    for (int i = 0; i < rc.length; i++) {
        left.addLast(rc[i][0]);
        ArrayDeque<Integer> midQueue = new ArrayDeque<>();
        for (int j = 1; j < rc[i].length - 1; j++) {
            midQueue.addLast(rc[i][j]);
        }
        mid.addLast(midQueue);
        right.addLast(rc[i][rc[i].length - 1]);
    }

    // ShiftRow / Rotate 연산
    // O(N) N = 100,000
    for (String operation : operations) {
        // ShiftRow인 경우
        if ("ShiftRow".equals(operation)) {
            left.addFirst(left.pollLast()); // O(1)
            mid.addFirst(mid.pollLast()); // O(1)
            right.addFirst(right.pollLast()); // O(1)
        }
        // Rotate일 경우
        else {
            mid.peekFirst().addFirst(left.pollFirst()); // O(1)
            right.addFirst(mid.peekFirst().pollLast()); // O(1)
            mid.peekLast().addLast(right.pollLast()); // O(1)
            left.addLast(mid.peekLast().pollFirst()); // O(1)
        }
    }

    // Queue에 담긴 값을 배열로 변환
    for (int i = 0; i < answer.length; i++) {
        answer[i][0] = left.pollFirst();
        ArrayDeque<Integer> midQueue = mid.pollFirst();
        for (int j = 1; j < answer[i].length - 1; j++) {
            answer[i][j] = midQueue.pollFirst();
        }
        answer[i][answer[i].length - 1] = right.pollFirst();
    }

    return answer;
}

---

💡 문제 풀이

ArrayDeque

 

풀이에 앞서 먼저 ArrayDeque라는 것에 대해 알아야 할 필요가 있다.

Deque란 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다.

사용해 보면 알 수 있겠지만 ArrayDeque에는 addFirst(), addLast(), pollFirst(), pollLast()라는 함수가 있는데 이 친구들을 통해 Stack과 Queue처럼 사용할 수 있다.

 

시간복잡도

 

문제에서 주어진 조건은 행과 열의 길이는 50,000 이하이며, 행의 길이 r과 열의 길이 c를 곱한 값은 100,000을 넘지 않는다.

따라서 행(r)의 길이가 50,000이면 열(c)의 길이는 20,000이 최대다.

operations의 길이도 100,000이기 때문에 최대 연산 횟수는 100,000 * 100,000인 100억 번의 연산이다.

그렇다면 우리는 O(N^2)의 형태로는 풀 수 없기 때문에 이중 포문을 통한 연산은 불가능하다.

 

이 문제에서는 ArrayDeque를 사용하여 푸는데 ArrayDeque를 통해 연산을 하게 되면 일반적인 배열의 복사가 아닌 주소값을 통해 연산이 가능하기 때문에 사용한다.

우리는 ArrayDeque를 3개 사용할 예정이며, 하나는 이중 ArrayDeque를 사용한다.

 

문제 풀이는 아래 입출력 예#3번 문제를 예로 들어 그림과 함께 설명해 보겠다.

 

 

ArrayDeque<Integer> left = new ArrayDeque<>(); // 좌측 열
ArrayDeque<Integer> right = new ArrayDeque<>(); // 우측 열
ArrayDeque<ArrayDeque<Integer>> mid = new ArrayDeque<>(); // 가운데 n열

left에는 가장 왼쪽의 열을 삽입할 예정이고, right에는 가장 오른쪽 열을 삽입할 예정이다.

mid 이름을 가진 ArrayDeque에는 남은 가운데 열들을 입력해 줄 예정인데 한 행씩 ArrayDeque에 넣어서 2차원 ArrayDeque를 만들 것이다.

 

// 초기 값 Queue에 입력
// O(N) -> N = rows * cols <= 100,000
for (int i = 0; i < rc.length; i++) {
    left.addLast(rc[i][0]);
    ArrayDeque<Integer> midQueue = new ArrayDeque<>();
    for (int j = 1; j < rc[i].length - 1; j++) {
        midQueue.addLast(rc[i][j]);
    }
    mid.addLast(midQueue);
    right.addLast(rc[i][rc[i].length - 1]);
}

이제 초기값을 위 코드로 입력시켜 준다.

 

 

설명보다는 그림이 편할 테니

왼쪽이 우리가 수행할 add와 poll연산, 오른쪽이 수행 후 결과라는 것을 알아두고 그림을 보면서 이해해 보자.

ArrayDeque를 통한 연산은 주소값을 이용하여 삽입과 삭제를 하게 된다. 따라서 각 연산의 시간복잡도는 O(1)이라는 것을 알아두자.

// ShiftRow인 경우
if ("ShiftRow".equals(operation)) {
    left.addFirst(left.pollLast()); // O(1)
    mid.addFirst(mid.pollLast()); // O(1)
    right.addFirst(right.pollLast()); // O(1)
}

ShiftRow

 

// Rotate일 경우
else {
    mid.peekFirst().addFirst(left.pollFirst()); // O(1)
    right.addFirst(mid.peekFirst().pollLast()); // O(1)
    mid.peekLast().addLast(right.pollLast()); // O(1)
    left.addLast(mid.peekLast().pollFirst()); // O(1)
}

Rotate

 

마지막으로 우리는 ArrayDeque를 통해 연산을 했기 때문에 문제에서 원하는 return 타입인 배열로 변환해 줘야 한다.

// Queue에 담긴 값을 배열로 변환
for (int i = 0; i < answer.length; i++) {
    answer[i][0] = left.pollFirst();
    ArrayDeque<Integer> midQueue = mid.pollFirst();
    for (int j = 1; j < answer[i].length - 1; j++) {
        answer[i][j] = midQueue.pollFirst();
    }
    answer[i][answer[i].length - 1] = right.pollFirst();
}

 

우리는 연산에서는 O(1)의 시간 복잡도를 가졌고, 초기에 배열을 입력할 때 O(N)의 시간 복잡도를 가졌다. 따라서 전체 시간은 O(N)으로 마무리할 수 있다. 그렇기 때문에 효율성 테스트는 무조건 통과한다.

---

👀 후기

프로그래머스 Level4 상당히 어렵다... 내가 혼자 도전한다면 이걸 풀 수 있을지 모르겠다.

알고리즘을 어떻게 생각해 내는 건지.... 이런 문제를 볼 때마다 너무 막막하지만 푸는 사람들이 있기에 신기하다..

코테 화이팅!!!