프로그래머스 월간 코드 챌린지 빛의 경로 사이클 문제 해설/코드 (파이썬)

문제 해설 코드만 궁금한 분은

GitHub - Rhyankwon/algorithms

 

일단 문제 설명부터 고고

사실 전에 현대차 소프티어 문제에서 약간 비슷한 문제를 풀어본 적이 있어서(풀지는 못함;; 아직 보류상태) 문제 이해가 엄청 어렵진 않았다. 간단하게 얘기하면 어떤 격자가 주어지는데 그 안의 각 격자 안에는 직진만 할수 있는 s, 좌회전만 할 수 있는 L, 우회전만 할 수 있는 R 신호가 각각 들어있다. 이 말은, 각 격자마다 상 하 좌 우 로 모두 갈 수는 있지만 시작 상태에서가 아니고서는 들어오는 방향과 격자의 상태(S, R, L)의 조합에 따라 그 다음에 이동하는 방향이 결정된다는 뜻이다. 각 격자마다 매번 한 방향으로만 갈 수 있기 때문에 시작 지점, 시작 지점에 출발하는 방향, 격자의 상태에 따라 못 가는 격자가 생길수도 있고 일정한 방향으로 사이클이 생기게 된다. 예시를 보면 쉽다.

입출력 예 3을 보면 R, R 이렇게 격자가 입력된 경우에는 왼쪽, 오른쪽과 같이 두개의 사이클이 생기게 된다. 왼쪽 사이클은, 윗쪽 격자는 왼쪽에서는 들어오고 오른쪽으로는 나가고 윗쪽으로는 아예 이동하지 않는 사이클이고 오른쪽은 그 반대이다.. 내가 말을 이상하게 하는 것 같지만 이해하고 나면 이렇게밖에..설명이 안된다. 아무튼 이렇게 두개의 사이클이 생길 때 각 사이클의 길이는 4가 되고 그래서 result로 [4, 4]를 리턴해주면 된다. 스택이나 재귀를 사용하면 풀 수 있는 문제이다. 결국 사이클을 모두 찾고 각 사이클마다 길이가 얼마인지를 찾아주면 되기 때문에 각 격자마다 생길 수 있는 모든 경로를 확인해보면서 사이클을 찾고, 이미 확인한 사이클안에 있는 경로는 모두 같은 사이클을 의미하기 때문에 다른 변수에 이미 확인한 경로 리스트를 만들어서 저장하고 그 부분은 스킵하면 된다. 나는 스택을 써서 풀었고, 가장 중요한 부분의 코드는 아마 아래 이부분..?

 

 

잘 풀린다. 모든 경로를 확인해야해서 시간이 길게 나오는건 어쩔 수 없다고 생각했지만 너무 긴것같아서; 나중에는 조금 더 최적화를 해보려고 노력해야할 것 같다. 그리고 다른 사람들 풀이를 보니까 훨씬 시간이 짧게 걸리는 코드도 있고, 음 스택을 사용한 사람들의 전반적인 논리는 다 비슷한 것 같은데 아마도 내가 슬라이싱이나 리스트 붙이기같은 코드들을 많이 사용해서 다른 사람들보단 시간이 조금 더 걸린 것 같다. 그리고 나는 S, L, R의 경우 들어오는 방향에 따라 나가는 경로를 미리 선언해서 활용했는데 다른 사람들의 풀이를 보니 뭐..무슨 규칙이 있나보다; 나는 그렇게까지는.. 모르겠지만 앞으로 배워볼 법 한 것 같다. 

 

--------------------------------------------------------------

 

여담) 다 풀고나서 예제 3개를 모두 통과하고 오 되겟넹^^했는데 테스트케이스에서 마지막문제를 제외하고 전부 틀렸다고 나와서 엄청 당황했다. 예제 3개를 전부 맞았는데 테스트케이스를 다틀린다니 분명 사소한 문제일 것 같은데 찾을 수가 없어서 30분이나 고민했다. 그리고 질문에 내 코드를 올리고.. 도움을 요청했는데 댓글을 보니...

'오름차순으로 정렬해보세요'

아놔 문제 조건을 보니 마지막에 오름차순 정렬을 해야한다 ㅜㅜㅜㅜ 이런걸로 질문이나 하는게 부끄럽기도 하고 문제를 제대로 안 읽은게 너무 후회된다..........흑흑 앞으론 잘 읽는걸로 ;;;

 

여담2) 이거는 레벨2라고 돼있긴 한데 레벨3정도는 그래도 되는 문제..인것같다. 엄청 어렵다 이런건 아닌데 이정도 풀면 그래도 코딩 아예 초보는 아닐거같은느낌

 

여담3) 월간 코드 챌린지 1번 (없는 숫자 더하기)는 너무 쉬워서 포스팅 안할거고 3번 (금과 은 운반하기)는 너무 어려워서 내가 직접 풀진 못할 것 같아서 포스팅 안한다. 지금 풀어보긴 하는데 딱봐도 다이나믹프로그래밍인데 내가 여태 dp를 풀어본적이 거의 없어서 그냥 혼자 한번 훑고 다른 사람 코드 보고 공부하는 용도로..만 풀어볼듯. 뭐 혹시 모르긴하지만ㅋㅋㅋㅋ내가풀수잇을지,,!