리트코드 143번 문제 풀이

문제 코드만 궁금하신 분은 링크

 

처음 생각했을 때 쉽겠는데? 했던 것 보다는 엄청나게 깔끔하게 풀이한건 아니라서 사실 누구 보여주기 부끄럽다.ㅋㅋㅋㅋ 근데 뭐..통과 된건 통과 된 거니까... 런타임 92ms, 메모리는 23.5mb를 사용해서 그냥저냥 적당한 코드를 짠 것 같다. 

 

아무튼 해설하자면, 우선 이 문제는 1 - 2 - 3 - 4 - 5 이런 식의 연결리스트가 있으면 1 - 5 - 2 - 4 -3 이런식으로 맨앞-맨뒤를 번갈아가는 식으로 연결리스트를 다시 정렬해야 하는 문제이다. 처음엔 조금 뭐지..싶었는데 잘 생각해보니, 1 - 2 - 3, 이런식으로 처음부터 중간까지는 정순으로, 5 -4 이런식으로 중간부터 마지막까지는 역순으로 정렬해서 사이사이에 배치만 잘 하면 되는 문제였다. 엄청나게 쉬운 문제일 줄 알았는데 그렇게까지 쉽게 풀리진 않았다.

 

잡설 : (특히 연결리스트는 내가 약한 부분이라서.. 내가 코딩에 강한 부분이 있나 싶긴 하지만 특히나 스택이랑 연결리스트는 내가 약한 부분이다. 연결리스트의 경우에는 항상 cycle이 나와서 뭔가 잘 안되고 스택의 경우에는 흠.. 그냥 깔끔하게 스택 코드를 짠 적이 별로 없다. 아무튼 리트코드에서 스택 카테고리에서 적당히 medium 수준의 난이도에서 40%대 정답률을 아무거나 눌러서 풀었는데 하필 연결리스트가 나왔다. 스택공부 하려고 한건데 연결리스트 공부만 해버렸네.. 뭐 도움은 되긴 했지만..)

 

아무튼 그래서 처음부터 끝까지 리스트를 순회하면서 중간노드를 찾아내는 과정이 처음으로 필요했다. 그 이후에는 처음부터 중간까지 노드를 큐에 넣고 중간부터 마지막까지의 노드를 스택에 넣었다. 스택을 사용해야 역순이 되니까.. 그렇게 하고나서 약간의 예외처리를 하니까 문제를 풀 수 있었다. 문제 풀이가 너무 더러운 것 같아서 다른사람들의 풀이도 좀 찾아봤는데 어쨋든 막 몇줄만에 풀리고 그런 문제는 아닌가보더라. 적당히 둘러보고 그냥 내 풀이에 만족하기로 했다.

 

캡쳐도 하고 이것저것 해서 글을 더 예쁘게 쓰고싶지만 사지방에서 쓰는거라 그런 과정들이 조금 많이 번거롭다. 이해 부탁드립니다 ㅋ 절대 귀찮은건 아니고..