행렬 테두리 확인하기 풀이/코드 (파이썬) 쉬운데 어렵게 푼 문제 LV2

코드만 궁금한 분은 깃허브 링크 눌러주세요!

GitHub - Rhyankwon/algorithms

 

 

문제 설명 ㄱㄱ

코딩테스트 연습 - 행렬 테두리 회전하기

전체 행의 갯수, 열의 갯수가 주어진다. 이 때 해당 행렬은 맨 왼쪽 위부터 1, 2, 3 ,4 ,5 ,6 ..이런식으로 증가하는 행렬로 정의된다. 이후 이 안에 있는 숫자들을 뒤섞을건데, 이 규칙은 다음과 같다. 행렬의 안에서 임의의 두 배열을 골라 그 두 배열을 포함하는 가장 작은 직사각형 크기만큼의 배열의 가장자리를 시계방향으로 한칸씩 이동시키는 것이다. 이 때 움직임이 발생하는 배열들 중 가장 작은 수를 리턴하면 되는데, 이 과정의 배열 섞기가 여러번 진행되는 경우 매 번의 답을 저장해서 리스트로 반환한다.

 

 

< 내 해설 논리 >

 

1. 마치 dfs하듯이 미리 direction을 정해둔다. 이동시에는 반드시 오른쪽, 아래, 왼쪽, 위 방향으로 진행되므로 [[0, 1], [1, 0]..] 이런 식으로 방향을 미리 설정한다.

d = [[0, 1], [1, 0], [0, -1], [-1, 0]] #애초에 완전탐색스러운 느낌으로 가려고 했던게 실수!

2. 정해진 가장자리에서만 움직일 수 있도록 if문에 설정. 가령 맨 위, 맨아래 행, 맨왼쪽 맨오른쪽 열 에서만 움직일 수 있도록. +traced 배열에 이미 진행한 곳의 행/열 위치를 저장해서 이미 온 곳으로 돌아갈 순 없도록 설정.

3. 한칸씩 움직이면서 새로운 값을 tmp_value로 저장, 해당 배열에는 이전 value 넣기.

4. traced 배열을 만들 때 traced_value배열도 만들어서 값도 같이 저장. 매번 모든 움직임이 끝날 떄 해당 배열의 최솟값을 뽑아서 answer 리스트에 추가.

5. 모든 움직임이 끝나면 answer 리턴.

 

 

말이 쉽지 생각보다 내게 그렇게까지 쉬운..문제는 아니였다. 거의 한달만에 코딩테스트 문제를 풀다보니까 감이 많이 떨어진 모양이다. ㅠㅠ

 

풀고 나서 다른사람이 푼 풀이를 봤는데 이게 훨씬 효율적이다.

 

어차피 맨 왼쪽 위부터 오른쪽 -> 아래 -> 왼쪽 -> 위 방향으로 움직이는건 자명하니까, 그냥 매번 range로 열/행만 필요한 만큼만 탐색한다. for i in range(왼쪽열, 오른쪽열+1)로 해서 배열[맨윗쪽행][i] 이런식으로 하면 맨 윗쪽 탐색이 끝난다. 이 때 매번 stack에 새로 탐색한 배열의 값을 새로 추가하고, 새로 탐색한 배열의 값은 stack[-2]로 넣어주면 깔끔하다. 마지막 answer에는 min(stack)으로.

 

내 방식으로 하는 경우 오른쪽(범위 이탈), 아래(이미 탐색한 구역), 왼쪽(범위이탈), 윗쪽(맞는 방향) 이런 식으로 일부 경우에서는 상당히 많이 필요없는 탐색을 하게되서 시간도 오래걸린다. 지금 구현해보니 거의 20배 가까운 차이가 난다. 그럴 수 밖에 없는게, 나는 필요없는 탐색에다가 이 구역을 탐색하는게 맞는건지 확인하는 과정에서 if문이 몇개가 들어가버리니까 시간 차이가 상당해진다.

 

 

 이렇게 깔끔하게 풀 수있는진 왜 생각을 못했지?ㅋㅋㅋㅋ LV2인데 나는 거의 3시간 걸려서 풀엇다. 아무래도 복잡하게 풀다보니까 범위같은것들이 헷갈려서..