★ solved.ac 난이도 : S4
(2022년 03월 28일 기준)
[문제 링크]
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
[풀이]
이 문제를 일반적인 반복으로 풀려면, 매우 오래 걸립니다.
(N=5000, M=5000일 때, 약 2.2억번의 반복 연산 추정)
그래서, 여기에서는 원형 연결 리스트와 이중 연결 리스트를 혼합해서 문제를 풀어보았습니다.
(O(NM) = 약 2500만)
리스트를 초기화하고 시작 지점을 설정한 다음, 링크를 M번 이동하고 값을 출력 후, 해당 노드를 삭제하는 것을 반복하였습니다.
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)