1158번 : 요세푸스 문제

링크드 리스트   리스트  리스트 리스트리스트.. 리스트리스트리스트리 스트리  스트리   스트리     스토리       티스토리...!!!!
내 티스토리 흥하자!!!!!!!!!!!!!!!!!

진짜 도저히 드립 생각이 안 났다.

 
링크드 리스트의 활용법과 출력부를 고민해야 하는 짬뽕 문제였다. 생각보다 출력부의 포맷을 맞추느라 고민을 좀 했었던..
쓰이는 빈도수가 아주 높은 링크드 리스트와, 다른 문제에서도 나올 수 있는 출력 형태에 대한 경험이 생긴 것 같아서 앞으로의 코딩에 좋은 도움을 얻을 듯한 문제!
 

생각보다 이해는 어렵지 않은 문제다. 당신이 도넛을 먹는데, 왜곡된 섭취 패티쉬에 감염되어 일정 구간을 두고 베어 먹고 싶어졌다. 한 입 베어문 이후 3센치를 지나서 베어 먹는 것을 반복하며 도넛을 다 먹고 싶은데, 그러다 보면 3센치를 지난 부분이 이미 이전에 베어 먹은 자리여서 허공에서 혀를 씹을 수도 있는 위험이 도사리고 있다. 하지만 당신의 페티쉬는 생각보다 강해서, 3센치를 지난 시점이 허공이라면 그 허공은 무시하고 이어서 계속 3센치를 가고 싶어한다고 한다. 그렇다면 도넛을 7구간으로 나누었을 때, 베어 먹는 구간의 순서는 어떻게 될까? 하는 문제이다.
 

윗 줄엔 도넛을, 아랫 줄엔 당신의 이상 취향을 표현했다.

문제의 요지는 매 순간 간택된 번호는 해당 배열에서 제거되어야 하고, 그 이후부터 다시 순번을 세는 것에 있다. 
단순히 매 순간의 순번을 세는 것이라면 3칸씩 이동하며 배열의 마지막을 넘어가는 index에만 신경을 쓰면 되겠지만
이 문제의 경우는 빈 공간을 무시하는 부분도 함께 알고리즘에 첨가되어야 한다.
 
 
나의 첫 번째 해결책은 위에 설명의 사고의 순서 그대로, 해당 크기(N)의 boolean 배열을 만들어서 false로 초기화 하고, 매 순번마다 index로 선택된 부분은 true로 바꾸며 출력하는 것이었다. 만약 다음 과정에서 배열을 확인했는데 true라면, 해당 부분은 이미 전에서 선택됐던 부분이라 생각하여 무시하고 다음칸으로 넘어가는 아이디어다.

 

첫 번째 for문은 배열의 개수만큼 진행하고, (어차피 모든 원소가 한 번씩 선택되면 끝나는 알고리즘이기 때문에 진행 개수가 배열의 length와 같아진다.) 안쪽의 두 번째 for문은 pointer을 3만큼 (k=3) 이동시키는 반복문이다. 단, 한 칸 이동 후의 배열이 true라면 비어 있는 공간으로 인식하여 인덱스를 하나 빼는 것으로 반복문을 한 번 더 진행시킨다.
 
추가적으로 출력부(answer)에 대하여 고민을 많이 했는데, <1, 2, 3>의 형태를 표현하기 위해서 처음과 마지막에 "<"/">" 문자열을 넣어두고, 다음 숫자에는 뒤에 ", "를 포함하여 문자열에 더해주었다. 그럼 결과물이 <1, 2, 3, > 가 되어버려 정답 포맷과 맞지 않게 되는데, 이 문제를 해결하기 위해 substring을 이용하여 마지막에 ", "를 지우고 ">"로 대체하는 방법을 사용했다. 개인적으로는 지저분하고 딱 떨어지는 느낌이 아니라 마음에 들진 않았다.
 

이런 방식으로 문제를 풀면 이렇게 얼척없는 크기와 속도의 결과와 마주한다. 본 결과는 해당 문제를 맞힌 사람 7320여명 중 7250등을 달성하는 쾌거를 이룩했으며, 내 두뇌의 무능함과 개발자로서의 자격을 끊임없이 되묻게해주는 핫소스맛 자극제가 되었다. 배열에 이중 for문이니 당연하다.. 역시 배열은 안 된다.. 배열은 안 돼.. 리스트.. 리스트를 가져와 헠헠..
 
 

그리하야 예쁘게 LinkedList와 단일 for문으로 예쁘게 만든 코드는 메모리를 2배!! 속도를 10배!!!!!!!!!! 줄여주었다.
리스트의 특성 때문에 알고리즘도 간단해지고, 고민할 부분도 사라졌다. 어차피 리스트는 remove를 하면 해당 노드가 줄어드니 pointer을 건들 필요도 없었으며, 단지 pointer가 list의 size를 넘어갈 때 size만큼 나누어주는 정도만 구현했으면 됐다. 단 주의할 점은, 3칸을 간다고 pointer에 3을 매번 더해주면 안 된다는 것이다. 만약 remove로 3번째 노드를 지우면 pointer은 그대로 3인데 노드는 사라져 실제 4 부분을 3의 pointer가 가리키고 있는 셈이 되므로, 삭제되는 노드까지 고려하여 k-1 만큼을 매번 더해주어야 맞는 방법이 된다.
 

pointer을 List에서 k씩 더했을 때 일어나는 일이다. 옳지 않음을 보임.

 
오늘은 리스트의 활용법 관련 문제를 풀어봤다. 개인적으로는 이런 문제는 별로 좋아하지 않는다. List 클래스를 아느냐 모르느냐가 결과에 큰 영향을 미치기 때문에 크게 수학적인 사고와는 상관이 없는 것 같아서.. 하지만 결국 난 Java의 개발자가 목표이고, List 등 여러 컬렉션 프레임워크들은 무수히 많이 쓰이는 클래스이기 때문에 숙지하는 것이 필수! 여러 라이브러리와 자료구조 클래스에 익숙해지고 충분히 체화하여 적재적소에 활용할 수 있게 노력합시다!