소잡기가 무슨 문제인지는 모르겠지만, n이 얼마인지만이 중요한 것이 아니라 시간복잡도가 중요합니다. n이 십만일 때 O(n)이나 O(nlogn)에 동작하는 코드는 당연히 통과가 되겠지만, 이 문제를 원형 리스트로 풀려고 하면 O(n^2)이 되기 때문에 통과될 수 없는 것이 당연합니다.
조세퍼스 문제 1은 n이 5000인데 이 때 O(n^2) 알고리즘으로 68ms가 걸리셨습니다. n^2은 2500만입니다. 그러면 n이 10만이면 얼마나 걸릴까요? n^2은 100억입니다. 대략 400배 정도 시간이 더 걸리겠죠?
조세퍼스 문제 2는 세그먼트 트리 등을 이용해서 O(nlogn)에 풀 수 있습니다만, 지금 수준에서는 상당히 어려울 것으로 보입니다. 다른 문제를 많이 풀고 나중에 시도하시는 걸 권장드립니다.
porrshe 5년 전
조세푸스1은 원형리스트구현해서 풀었습니다.
그런데 조세푸스2에 똑같은 소스를 넣으니 시간초과가 걸리네요.
조세푸스2는 n이 십만입니다.
예전 소잡기라는 문제를 풀때 n이 십만이여서 충분히 돌아갈 거 라고 생각했어요.
왜 조세푸스2는 안되는걸까요? 조세푸스2 원형리스트나 리스트로 푸신분 계시나요?
만약 푸신분 계신다면 어디서 최적화를 시켜야 하는지,어느 부분에서 시간이 많이걸리는지 조언 해주실 수 있으신가요!
내일은 이중연결로 풀어볼생각인뎁.. 도와ㅓ주세요!