프로그래머스 - 행렬과 연산

문제 설명

행렬이 주어진다.

주어진 연산에 의해 행렬이 이동하고 난 후 결과를 출력하는 단순한 문제이다.

하지만 이문제는 효율성 측정되는 문제라 최적화를 생각해야한다.

shiftRow, rotate 두가지 명령만이 존재한다.

일반적인 시뮬레이션으로 구현하면 shiftrow는 최대 n *m 번의 연산이 필요하고 rotate는 n+m-2번이 필요하다.

그리고 명령어는 최대 10만이라 정확성은 통과할지라도 효율성은 당연히 실패한다.

최적화하기에 시도했던 방법은 연산의 일부를 합치면 최적화가 가능한가 그려봤다. 하지만 나오지 않았다.

2022 테크 여름인턴십 코딩테스트 해설

해당 내용을 참고하였더니 자료구조의 쓰임을 잘 알고있는지 체크하는 문제였다.

각각을 단순한 시물레이션이아닌 자료구조의 최적화를 유도했던 문제였다.

rotate시 행렬을 추상화하여 각각을 자료구조에 담는다.

전체 행렬을 추상화하면 이렇게 된다. 그렇게 되면 rotate시

1. A에서 첫번째에 원소를 뽑아 B의 첫번째로 담는다
2. B의 마지막에서 뽑은 원소를 C의 원소로 담는다
3. C의 마지막에서 뽑은 원소에서 D의 마지막 원소로 담는다
4. D의 첫번째 원소를 뽑아 A의 마지막 원소로 담는다

rotate는 o(1)로 가능하다 하지만 shiftrow는 어떻게 할것인지 고민해야한다.

결국 왼쪽기둥 오른쪽 기둥 가운데 여러 기둥들이 존재하는 가운데 맨 밑에 있는 왼쪽,오른쪽 기둥 마지막 원소 2개와 가운데 기능을 그냥 위로 올리면된다. 3번의 연산은 곧 o(1)의 시간복잡도를 가지게 된다.

주의사항이 있다.

링크드리스트(덱) 자료구조를 이용하면 삽입,삭제가 간단하다.

하지만 get(i)를 통해 탐색하는 방법을 지향해야 한다.

get메소드를 통한 접근은 결국 처음부터 끝까지 탐색할 수 있기 떄문에 이부분에서 3,4,5 효율성이 꺠지게 될 것이다.그렇기 때문에 자료구조를 get을 통합 접근이 아닌 바로바로 제거하면서 넣어줘야 한다.

마지막 정답 배열에 복사할 때도 그렇게 해야한다!

풀이

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

		int N = rc.length;
		int M = rc[0].length;

		LinkedList<Integer> l = new LinkedList<>();
		LinkedList<Integer> r = new LinkedList<>();
		LinkedList<LinkedList<Integer>> m = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			l.add(rc[i][0]);
			r.add(rc[i][M - 1]);
			m.add(new LinkedList<>());
			for (int j = 1; j < M - 1; j++) {
				m.get(i).add(rc[i][j]);
			}
		}

		for (String cmd : operations) {
			if (cmd.equals("Rotate")) {
				int val = l.pollFirst();
				m.peekFirst().offerFirst(val);

				val = m.peekFirst().pollLast();
				r.offerFirst(val);

				val = r.pollLast();
				m.peekLast().offerLast(val);

				val = m.peekLast().pollFirst();
				l.offerLast(val);
			} else {
				l.offerFirst(l.pollLast());
				r.offerFirst(r.pollLast());
				m.offerFirst(m.pollLast());
			}
		}

		int answer[][]=new int[N][M];

		for(int i=0; i<N; i++){
			answer[i][0]=l.pollFirst();
			answer[i][M-1]=r.pollFirst();
			int j=1;
			for(int val: m.pollFirst()){
				answer[i][j++]=val;
			}
		}

		return answer;
	}