행렬과 연산

2025-11-01

#JAVA#프로그래머스

2분

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
주어진 행렬 rc에 대해 두 가지 연산을 수행해야 한다.
- ◦
  "ShiftRow" : 전체 행을 아래로 한 칸씩 이동
- ◦
  "Rotate" : 행렬의 가장자리를 시계 방향으로 한 칸 회전

•
여러 번의 연산을 순서대로 수행한 후의 행렬을 반환해야 한다.

•
시간 효율을 고려해야 함 — 단순 배열 기반으로 회전시키면 시간초과 발생

문제 풀이

이 문제는 처음보자마자 배열로 행렬을 만들어서 하면 절대 안될거라고 생각했다.

그래서 생각한게 Deque를 사용해서 계산하면 앞뒤로 넣고, 뺄 수 있으니 더 빠르게 계산이 가능할 것이라고 생각했다.

그래서 처음에는 단순하게 ArrayList<ArrayDeque> 를 이용해 각 행을 deque로 저장하고, Rotate 연산 시 두 번의 for문으로 직접 앞뒤 원소를 하나씩 밀고 당기는 방식을 사용했다.

Java

for(int j=0;j<r;j++){
    if(j!=0)
        a.get(j).removeFirst();
    if(j==r-1)
        break;
    a.get(j).addFirst(a.get(j+1).getFirst());
}
for(int j=r-1;j>=0;j--){
    if(j!=r-1)
        a.get(j).removeLast();
    if(j==0)
        break;
    a.get(j).addLast(a.get(j-1).getLast());
}

하지만 이렇게 하면 각 회전마다 $O(r)$ 의 시간이 들고,

연산 수가 많을 때 시간초과가 발생한다.

핵심 아이디어

이 문제는 “행렬의 전체를 움직이지 않고, 경계선만 빠르게 회전시킬 수 있느냐”가 포인트다.

그래서 행렬을 세 부분으로 분리했다.

Plain text

[왼쪽 열] [가운데 중간 행들] [오른쪽 열]

이렇게 세 부분을 각각 Deque으로 관리하면 다음과 같은 장점이 생긴다.

•
ShiftRow → 세 deque 각각을 맨 앞/뒤에서 한 칸씩 옮기면 끝 ( $O(1)$ )

•
Rotate → 경계 네 구역만 한 칸씩 옮기면 끝 ( $O(1)$ )

즉, 한 번의 연산을 상수 시간에 처리할 수 있다.

세부 구현

1
분리
Java
for (int i = 0; i < r; i++) { left.add(rc[i][0]); right.add(rc[i][c-1]); ArrayDeque<Integer> mid = new ArrayDeque<>(); for (int j = 1; j < c-1; j++) mid.add(rc[i][j]); middle.add(mid); }

2
ShiftRow 연산
- •
  아래로 한 행씩 이동
Java
left.addFirst(left.removeLast()); middle.addFirst(middle.removeLast()); right.addFirst(right.removeLast());

3
Rotate 연산
- •
  시계 방향으로 한 칸 회전 (왼쪽 → 위 → 오른쪽 → 아래 → 다시 왼쪽)
Java
middle.peekFirst().addFirst(left.removeFirst()); right.addFirst(middle.peekFirst().removeLast()); middle.peekLast().addLast(right.removeLast()); left.addLast(middle.peekLast().removeFirst());

4
결과 조립
- •
  세 덱을 다시 하나의 2차원 배열로 합쳐서 반환

최종 코드

Java

import java.util.*;

class Solution {
    public int[][] solution(int[][] rc, String[] operations) {
        int r = rc.length;
        int c = rc[0].length;
        int[][] answer = new int[r][c];
        
        ArrayDeque<Integer> left = new ArrayDeque<>();
        ArrayDeque<Integer> right = new ArrayDeque<>();
        ArrayDeque<ArrayDeque<Integer>> middle = new ArrayDeque<>();
        
        for(int i=0;i<r;i++){
            left.add(rc[i][0]);
            right.add(rc[i][c-1]);
            
            ArrayDeque<Integer> mid = new ArrayDeque<>();
            for(int j=1;j<c-1;j++){
                mid.add(rc[i][j]);
            }
            middle.add(mid);
        }
        
        for(int i=0;i<operations.length;i++){
            String op = operations[i];
            
            if(op.equals("Rotate")){
                middle.getFirst().addFirst(left.removeFirst());
                
                right.addFirst(middle.getFirst().removeLast());
                
                middle.getLast().addLast(right.removeLast());
                
                left.addLast(middle.getLast().removeFirst());
            }
            else{
                left.addFirst(left.removeLast());
                middle.addFirst(middle.removeLast());
                right.addFirst(right.removeLast());
            }
        }
        
        for(int i=0;i<r;i++){
            answer[i][0] = left.removeFirst();
            int idx = 1;
            for(int val : middle.removeFirst()){
                answer[i][idx++] = val;
            }
            answer[i][c-1] = right.removeFirst();
        }
        return answer;
    }
}