행렬과 연산

https://school.programmers.co.kr/learn/courses/30/lessons/118670

프로그래머스

 

Level 4

 

단순한 로직으로 구현에 가까운 문제이지만 솔루션을 위한 아이디어 도출이 상당히 빡센 문제

익숙한 클래스만 사용하지 말고 더 좋은 더 효율적인 클래스를 평소에도 찾아야하는 이유가 이건가 싶다.

 

최근 대부분 코딩테스트 문제들은 생소한 알고리즘은 둘 째치더라도

종종 우선순위 큐나 이 문제의 해답 열쇠인 덱을 시험 당시에 잊고 있으면 효율성 통과는 둘째치고 

정확성이라도 뚫어 보기 위해 비효율적인 자료구조로 짜다보면 오히려 시간만 버리고 뒷 문제를 못푸는 경우가 생긴다.

알고리즘이면 그냥 맘편히 포기하고 넘어가기라도 하지;;

 

일단 나 또한 이 문제를 풀 당시 덱을 사용할 생각을 못하고 무작정 2차원 배열에 연산을 통해 구현했는데,

정확성도 일부만 통과했고 효율성은 당연히 전부 통과하지 못했다. 

 

그래서 오늘은 지난 날의 오류를 고쳐보기 위해 공식해설을 참고하여 솔루션을 도출해보았다. 

 

일단 이 문제는 굉장히 빡빡한 효율성 케이스를 가지고 있다. 최초에 해설없이 덱 개념만 익히고 다시 문제를 풀어보았는데, 기존 O(n2) 에서 상당히 시간복잡도를 줄였음에도 불구하고 정확성은 통과하더라도 일부 효율성을 통과하지 못했다. 그래서 더 오랜 시간 고민했지만 결국 해답을 찾지 못해 공식 해설을 보고 이 문제는 O(1) 이라는 아주 아주 효율적인 구현방식이어야만 통과할 수 있다는 것을 알았다. 

 

내가 혼자 구현한 방식은 줄바꿈 연산의 경우에는 덱의 메소드를 이용해 간단하게 구현했고 

문제의 회전 연산은 다음과 같이 구현했다. 

 

 

2차원 덱을 이용해 0번 째, n-1번 째 원소들만 교체해주는 방식으로 기존에 무식하게 2차원 배열을 싹 엎어버리는 O(n2) 에서 O(n)으로 상당히 시간복잡도를 줄였는데도 불구하고 효율성 테스트를 통과하지 못했다. 풀이를 참고한 결과 상당히 놀라운 풀이법을 알 수 있었는데, 행렬의 틀에서 벗어나야만 풀 수 있는 듯한 느낌을 받았다. 

 

 

행렬을 3개의 영역으로 쪼개 위와 같이 연산만 해준다면 무려 O(1) 로 줄일 수 있다는 것이었다. 

구현 또한 처음 데이터 입력단계 그리고 마지막 반환 시 형변환 단계만 까다로울 뿐이지 메인 로직 또한 기존보다 훨씬 단순하게 작성할 수 있었다. 

 

이번 문제는 정말 기존의 알고리즘에 의존하는 문제가 아닌 개인의 틀에 벗어난 창의력이 아니면 풀지 못했을 거라고 생각하며 오랜만에 좋은 문제를 만날 수 있어서 흥미로웠다. 

 

import java.util.*;

class Solution {
    public int[][] solution(int[][] rc, String[] operations) {
        int maxRow = rc.length;
        int maxCol = rc[0].length;
        int[][] answer = new int[maxRow][maxCol];
        Deque<Deque<Integer>> midDeque = new LinkedList<Deque<Integer>>(); //중간 2차원 덱
        Deque<Integer> leftDeque = new LinkedList<Integer>(); //우측 덱
        Deque<Integer> rightDeque = new LinkedList<Integer>(); //좌측 덱

        for (int[] row : rc) { //데이터 입력
            Deque<Integer> midSubDeque = new LinkedList<Integer>();
            for (int col = 0; col < maxCol; col++) {
                if (col == 0) {
                    leftDeque.addLast(row[col]);
                } else if (col == maxCol - 1) {
                    rightDeque.addLast(row[col]);
                } else {
                    midSubDeque.addLast(row[col]);
                }
            }
            midDeque.add(midSubDeque);
        }

        for(String operation : operations) { //연산 실행
            if(operation.equals("ShiftRow")) { //줄바꿈
                leftDeque.addFirst(leftDeque.pollLast()); //좌측 덱의 마지막 원소를 맨 앞으로 보냄
                rightDeque.addFirst(rightDeque.pollLast()); //우측 덱의 마지막 원소를 맨 앞으로 보냄
                midDeque.addFirst(midDeque.pollLast()); //중간 덱의 마지막 덱을 맨 앞으로 보냄
                //최종적으로 맨 아래 줄이 맨 위로 올라오는 것과 같은 연산이 됨
            }else { //회전, (0,0) 부터 시계 방향으로 진행
                midDeque.peekFirst().addFirst(leftDeque.pollFirst()); //좌상단 연산
                rightDeque.addFirst(midDeque.peekFirst().pollLast()); //우상단 연산
                midDeque.peekLast().addLast(rightDeque.pollLast()); //우하단 연산
                leftDeque.addLast(midDeque.peekLast().pollFirst()); //좌하단 연산
            }
        }

        for(int cnt = 0; cnt < maxRow; cnt++) { //반환을 위한 데이터 입력
            answer[cnt][0] = leftDeque.pollFirst();
            answer[cnt][maxCol-1] = rightDeque.pollFirst();
            Deque<Integer> midSubDeque = midDeque.pollFirst();
            for(int idx = 1; idx < maxCol-1; idx++) {
                answer[cnt][idx] = midSubDeque.pollFirst();
            }
        }

        return answer;
    }
}