알고리즘 알고파! 알고라파덕
안녕하세요~ 알고라파덕입니다!
이번 문제는 JOSEPHUS라는 문제로!! 원탁의 기사같은 연결리스트 문제입니다!!
- 문제 개요
입력에서 테스트 케이스가 주어지면 테스트 케이스마다 N명의 사람과 1번이 죽었을 때 그 사람으로 부
터 몇 번째인 사람이 죽을 K가 주어집니다. 1번부터 시작하여 차근차근 죽어가고 마지막으로 살아남는
2명의 사람을 출력하는 문제가 되겠습니다.
- 문제 풀이
N개의 입력을 받고 1번부터 N번까지 연결리스트를 구축을 합니다. 그러면 위치는 마지막 N번이 되어있습니다. pre를 N번, cur을 1번으로 하게끔 1~n을 동적할당 합니다.
여기서부터 pre의 next를 cur의 next로 바꾸어주어 1번을 지우고 pre는 그대로, cur은 다음으로
넘어갑니다. 총개수를 감소시키고, 짤라야하는 개수를 k-1로 설정합니다. 그리고 짤라야하는 개수만큼
pre와 cur을 하나하나 이동하면서 (pre = cur; cur = cur->next;) 짤라야하는 개수를 하나씩 줄입니다.
짤라야 하는 개수가 0이 된다면 또 pre 다음의 사람을 없애고 (pre->next=cur->next; cur = cur->next)
짤라야하는 개수를 k-1로 다시 설정하고 총개수를 감소시킵니다.이 과정을 반복하여 총 개수가 2개가 되면 남은 2개의 연결리스트를 작은 순서부터 출력을 합니다.
시험들이 다 끝나면 연결리스트 기본적인 구현방법과 설명, 그리고 앞에서 못했던 BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색)을 알고리즘 설명 카테고리에 포스팅 하겠습니다~
소스가 필요하신 분은 댓글을 달아주세요~