23.07.10 파이썬 코딩 퀴즈#262 행렬과 연산(프로그래머스 스쿨)

이번 문제는 행렬과 연산 문제이다.

문제는 굉장히 단순하다

행렬에 적용 가능한 연산은 총 두가지 이고, 첫번째는 ShiftRow 이다

ShiftRow 명령은 모든 행을 아래로 한칸씩 이동한다. 즉 마지막 행이 가장 위로 올라오고 나머지는 그대로 유지된다.

다음은 Rotate 명령어 이다.

해당 명령어의 행렬의 바깥쪽의 원소들을 시계방향으로 움직인다. 기준점을 기준으로 시계방향이 아니라, 행렬의 바깥쪽 원소들만 통째로 시계방향으로 움직인다.

전달받은 rc 행렬에 비대칭은 존재하지 않는다.

입출력 예제는 특별히 챙겨볼 내용 없이 3번만 확인해보자.

보시다가 시피 Rotate 명령을 수행하게 되면 중간에 위치한 rc[1][1], rc[1][2] 는 움직이지 않는다.

바로 생각나는 대로 코드를 작성해 보았다.

굉장히 단순하고 직관적인 코드를 작성해서 제출해 보았다.

정확성 테스트 에서 모두 시간초과에 걸렸다.

다음은 좀 공을 들였다.

먼저 좌표쌍 (i, j)들을 값으로 가지는 dict()를 만들어 정리하였고,

전달받은 operations 들을 바로 수행하지 않고 묶어서 같은 연산자들끼리 묶어서 순서대로 처리하는 방향으로 작성하였다.

여기서 반복횟수를 정할 cnt 는 만약 shiftrow 를 수행해야 한다면 수행할 연사자들의 길이를 전체 행의 개수로 나눈 나머지를, 반대로 Rotate를 수행해야 한다면 미리 구해둔 t값 (행*2 + 열*2 - 4)으로 나눈 나머지를 사용하기로 했다.

그렇게 이동된 좌표를 활용해서 다시 answer을 만들어 주는 방법인데...

효율성 테스트에서 5문제가 시간초과 에 걸린다.

 

다른 아이디어를 생각해보자.

rowshift 자체는 큰 문제는 아닌것 같아 rotate만 확인 해 보자.

먼저 4 x 6 배열에서 rotate 수행히 변하게 되는 셀은 노란색 셀이고, 그 갯수는 16개 이다.

(0,0)을 기준으로 보게 되면, 5회 실행했을때 (0,5)에 도착하게 된다.

다시 (0,0)을 기준으로 7회를 실행하게 되면 (2,5)에 도착하게 된다.

또 (0,0)을 기준으로 10회 실행시 도착 좌표는 (3,3)이 된다.

마지막으로 16회 실행하게 되면 원점으로 돌아온다.

 

(0,3)을 기준점으로 10회 rotate를 시행한다고 가정해 보자.

먼저 행이동을 하게 되면 (0,5)까지 이동하게 된다. (2회 소요)

그 다음 막혔기 때문에 열이동을 하게 되는데, (3,5)까지 내려온다 (3회 소요)

그리고 다시 막혔기에 (3,0)까지 왼쪽으로 이동하게 된다.

여기서 순수 값의 증감을 따지게 되면

시작 좌표[0, x] 를 기준으로 x+i 가 c보다 작을때까지 증가시켜 준다.

그 다음 시작 좌표[0] 값을 r 보다 작을때까지 증가시켜주고, 

마지막으로 x값을 다시 x-i 가 0이 될때까지 감소시켜 준다.

 

이를 응용하여 한번에 rotate를 수행하는 함수를 만들어보자.

먼저 move_cell()이란 함수를 정의해 주었다.

전달받은 d 를 기준으로 어디로 우선 움직일지를 정하고 ,이동 가능한 칸수를 확인 후 한번에 상하좌우로 움직이도록 설정해 보았다.

그리고 전달받은 operations 는 순서대로 정리해서 cmds 에 횟수와 명령어를 쌍으로 넣어주고

이를 반복문을 통해 돌면서 실행하도록 하였다.

그리고 이때 미리 추출한 각 좌표들의 위치를 확인하여 어느 방향으로 이동할 건지를 계산해서 move_cell()을 실행해 준다.

효율성 테스트 2,4,7번에서 시간 초과에 걸린다... 하 .. 머리가 아프다..

 

여기저기 해설을 찾아보고, 어떤 방법으로 접근해야 하는지 참고하였다.

만약 위와 같이 3x4 행렬이라고 가정할 때, 왼쪽과 오른쪽 그리고 가운데 부분을 따로 나누어 deque()를 활용해서 이동 정리 하는 방법이 최선의 해결책이라고 한다...

 

힌트를 보자마자 바로 코드로 작성해서 통과를 했다...

 

사실 제일 처음 생각한 방법이 행렬을 쪼개서 정리하는 거였지만, deque 까지는 생각을 못했던지라, 각 위치값을 좌표로 생각해서 정리하는 방법으로 실행했었는데....

deque 를 사용하여 바로바로 명령어를 처리하는 방법이 더 빨랐다.. 심지어 명령어를 묶어서 처리하지도 않았는데...

위는 바로바로 명령어를 처리하여 통과한 코드이고, 아래는 명령어를 다 묶어서 한번에 처리한 모습이다...

즉 그렇게 큰 시간차이는 없으나, 그래도 명령어를 묶어주는게 더 빠르긴 하다...

솔찍히 해설을 보지 못했다면, 몇일은 더 시간을 잡아 먹었을 문제이다...