마음만은 새내기

항상 초심을 잃지 않고 생활하겠습니다~!

프로그래밍/Baekjoon Online Judge

BOJ 1158번(요세푸스 문제) 문제 풀이

동동매니저 2019. 1. 28. 20:51

★ 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번 이동하고 값을 출력 후, 해당 노드를 삭제하는 것을 반복하였습니다.


[소스 코드]

만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)