[백준/1158] 요세푸스 문제 | 파이썬 연결리스트 | N번째 원소
·
PS/BOJ&Programmers
요세푸스 문제2년 전 풀었던 요세푸스...! 다시 풀려니까 로직은 생각나는데 정확한 구현이 떠오르지 않아 다시는 까먹지 않으려고 포스팅한다. (문제 바로 가기) 알고리즘순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 계속 해서 K 번째 사람을 제거하는데, 여기서 문제는 제거된 K를 제외하고 배열을 재생성해야 한다.이 문제의 연산 범위는 (1 ≤ K ≤ N ≤ 5,000)이며, Python은 1초에 약 5천만번의 연산이 가능하다.배열 순회하면서 K를 찾고, 배열을 재생성해도 O(N**2) 즉, 5000**2 = 2500만번 정도 수행한다.따라서 연산마다 배열을 재생성해도 충분한 시간이다..
