프로그래머스 행렬과 연산 자바 풀이

문제 링크

문제 풀이 시간 : 1시간

문제 요약

주어진 행렬 rc에 대해 두 가지 연산을 수행해야 한다.
여러 번의 연산을 순서대로 수행한 후의 행렬을 반환해야 한다.
시간 효율을 고려해야 함 — 단순 배열 기반으로 회전시키면 시간초과 발생

문제 풀이

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

그래서 생각한게 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)$ )

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

세부 구현

분리
ShiftRow 연산
Rotate 연산
결과 조립

최종 코드

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;
    }
}

행렬과 연산

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

실패 코드

핵심 아이디어

세부 구현

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기