[자바] 프로그래머스 - 행렬과 연산 (Lv4, Java)

문제 : Programmers-행렬과 연산

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• Linked List, Deque
  
  • 이 문제에서는 양방향에서의 삽입, 값 획득이 O(1)로 이루어질 수 있는 자료구조를 사용해야 한다. 따라서 Linked List 혹은 Deque에 대한 개념을 알고 있어야 풀 수 있다. 내 코드에서는 둘 다 사용하지만, 둘 중 하나로만 진행해도 동일한 결과를 얻을 수 있다.

 

 

  rc가 r*c 크기의 배열이라고 할 경우, 이 문제의 경우 그냥 배열 자체만 보고 진행을 하게 되면 shiftRow는 배열의 모든 원소를 건드려야 하므로 O(r*c)가 필요하고, rotate는 맨 위와 맨 아래 행, 그리고 좌우의 열을 건드려야 하므로 O(r+c)가 필요하다. 하지만 당연히 이렇게 짜면 효율성 테스트를 통과할 수 없다.

 

 

  내가 프로그래머스를 잘 안하는 이유가 이것때문인데, 정확성 테스트는 10초라고 해두고 효율성 테스트는 대충 '언어별로 작성된 정답 코드의 실행 시간의 적정 배수'라고 해놨다. 저거 10초의 배수도 아니다 ㅋㅋㅋ 대충 한 0.1~0.2초 걸어둔 것 같다. 대강이라도 어느정도 시간을 요구하는질 알아야지 사람들이 연습하면서 자신의 풀이의 시간복잡도 따져보고 이건 되겠다, 이건 안되겠으니 난 더 지식을 알아야 한다 판단할 수 있다고 본다. 코테에서야 '니가 생각하는 최선으로 함 짜봐'라는 식으로 생각할 수 있으니 변별력일 수 있지만, 코딩테스트 '연습'인데 연습할 수 있게 그래도 어느정도 시간 기준은 달아놔줘야 한다고 본다. 적어도 leetcode처럼 시간 복잡도로라도 달아놔줘야 연습하는 사람들이 연습을 할 수 있다고 본다. 뭐 사람마다 생각이 다를 수 있지만, 개인적으로는 로직을 전체적으로 구성하고 시간복잡도, 메모리복잡도 따져보는 설계과정이 끝난 후 코드를 짜는게 연습이지, 뭐 통과될 때 까지 왜 효율성 테스트를 통과할 수 없는지는 모르겠지만 대충 계속 바꿔보면서 넣어보는 과정은 짜증만 날 뿐이지 연습이 될거라고 보진 않는다.

 

 

  아무튼 그럼 어떻게 효율성을 통과할 수 있을지 생각해보자. 대충 자기가 생각하는 최선의 방법을 쓰면 되는데, 내가 생각하는 최선의 방법은 아래처럼 나눠서 생각하는 것이다. 좌, 우의 세로방향은 LinkedList 혹은 Deque로 처리하고, 중간부분은 LinkedList<Deque>라던지, Linked<LinkedList> 라던지, Deque<Deque> 라던지.. 마음에 드는걸로 고르면 된다.

 

 

ShiftRow

  좌우의 세로부분을 col1, col2라 하고, 중간에 있는 가로부분들을 row, row들을 다시 묶어둔걸 rows라고 하겠다. 코드로 나타내면 Deque col1, Deque col2, List<Deque> rows 와 같은 형태이고, rows 내의 Deque 각각이 row이다. ShiftRow 명령의 경우엔 그럼 다음과 같은 로직으로 변경된다.

 

1. col1에서 마지막껄 빼내서 맨 앞에 넣는다. -> O(1)

2. rows에서 마지막 row를 빼서 rows의 맨 앞에 넣는다. -> O(1)

3. col2에서 마지막껄 맨 앞에 넣는다. -> O(1)

 

  과정을 그려보면 다음과 같다.

 

 

Rotate

  Rotate도 마찬가지로 다음과 같이 변경된다.

 

1. col1의 맨 앞껄 빼서 rows 첫 번째 row의 맨 앞에 넣는다. -> O(1)

2. rows의 첫 번째 row의 마지막껄 빼서 col2의 맨 앞에 넣는다. -> O(1)

3. col2의 마지막껄 빼서 rows 마지막 row의 마지막에 넣는다. -> O(1)

4. rows의 마지막 row의 맨 앞껄 빼서 col1의 마지막에 넣는다. -> O(1)

 

  이번에도 과정으로 그려보면 다음과 같다.

 

 

 

따라서 각 operations마다 각 O(1)로 처리가 가능하고, 이렇게 되면 실제로 0.1초가 안걸려서 효율성 테스트를 통과할 수 있다. 주의점은 c가 2인 경우엔 중간부분이 없으므로 그 부분은 생각하면서 짜야 한다.

 

 

---

 

코드 : github

import java.util.ArrayDeque;
import java.util.LinkedList;

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    int r, c;
    ArrayDeque<Integer> col1, col2;
    LinkedList<ArrayDeque<Integer>> rows;

    private void init(int[][] rc) {
        r = rc.length;
        c = rc[0].length;

        col1 = new ArrayDeque<>();
        col2 = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            col1.add(rc[i][0]);
            col2.add(rc[i][c-1]);
        }

        rows = new LinkedList<>();
        for (int i = 0; i < r; i++) {
            ArrayDeque<Integer> tmp = new ArrayDeque<>();
            for (int j = 1; j < c-1; j++) {
                tmp.add(rc[i][j]);
            }
            rows.add(tmp);
        }
    }

    private int[][] getAnswer() {
        int[][] ans = new int[r][c];
        for (int i = 0; i < r; i++) {
            ans[i][0] = col1.pollFirst();
            ans[i][c-1] = col2.pollFirst();
        }
        int i = 0;
        for (ArrayDeque<Integer> row : rows) {
            for (int j = 1; j < c-1; j++) {
                ans[i][j] = row.pollFirst();
            }
            i++;
        }
        return ans;
    }

    private void rotate() {
        if (c == 2) {
            col2.addFirst(col1.pollFirst());
            col1.addLast(col2.pollLast());
            return;
        }
        rows.peekFirst().addFirst(col1.pollFirst());
        col2.addFirst(rows.peekFirst().pollLast());
        rows.peekLast().addLast(col2.pollLast());
        col1.addLast(rows.peekLast().pollFirst());
    }

    private void shiftRow() {
        rows.addFirst(rows.pollLast());
        col1.addFirst(col1.pollLast());
        col2.addFirst(col2.pollLast());
    }

    public int[][] solution(int[][] rc, String[] operations) {
        init(rc);
        for (String op : operations) {
            switch (op.charAt(0)) {
                case 'R' : rotate();    break;
                case 'S' : shiftRow();  break;
            }
        }
        return getAnswer();
    }
}