💡문제 분석 요약

https://www.acmicpc.net/problem/1158

요세푸스 문제 - n, k를 입력받아 1부터 n까지 n개의 숫자를 원형 리스트로 두고 (k - 1)개를 건너뛰고 k번의 요소를 제거한다. 이후 그 과정을 반복하여 제거한다.

💡 n = 7, k = 3 일 때, 숫자 리스트 1 2 3 4 5 6 7에서

1 2 4 5 6 7 | 3 → 1,2를 건너뛰고 3 제거 (target index = 2)
1 2 4 5 7 | 3 6 → 4,5를 건너뛰고 6 제거 (target index = 4)
1 4 5 7 | 3 6 2 → 반복 .. (target index = 1)
1 4 5 | 3 6 2 7 → 반복 .. (target index = 3)
1 4 | 3 6 2 7 5 → 반복 .. (target index = 2)
4 | 3 6 2 7 5 1 → 반복 .. (target index = 0)

3 6 2 7 5 1 4 → 정답 리스트

💡알고리즘 설계

• 숫자 리스트 josephus를 만든다.
• 리스트는 0부터 시작이므로 index = (k-1)번째 요소를 정답 리스트에 넣어준다.
• 해당 요소를 Josephus에서 제거한다.
• 이후 다음 타겟을 찾기 위해 반복하며 index에 (k-1)를 더해 제거할 요소를 찾는다.
• 이 때 index가 josephus의 길이보다 큰 경우 (index - josephus 길이)를 통해 제거해야 할 index를 찾아준다.
• josephus 길이가 0이 될 때까지 반복~..

💡코드

import sys

def print_ans(num) :
    print("<", end="")
    for n in num :
        print(n, end="")
        if n != num[-1] :
            print(", ", end="")
    print(">")

def Josephus_prob(n, k) :
    josephus = [i for i in range(1, n + 1)]
    answer = []
    idx = k
    for i in range(n) :
        length = len(josephus)
        while idx >= length :
            idx -= len(josephus)
        answer.append(josephus[idx])
        josephus.pop(idx)
        idx += k
    print_ans(answer)

n, k = map(int, sys.stdin.readline().split())
Josephus_prob(n, k - 1)

💡시간복잡도

for loop를 n번 순환하며 요세푸스 문제의 제거요소를 찾고 출력 시 n번 순환하기 때문에 총 O(2n)의 시간복잡도를 가진다. 하지만 n의 값이 커지면 O(n)과 O(2n)은 같아지므로 O(n)

💡 틀린 이유

• 출력형식을 고려하지 않고 list로 출력함

💡 틀린 부분 수정 or 다른 풀이

• 정답 출력 형식을 맞춰서 수정함
  • print()를 이용하여 출력할 때 옵션을 주지 않는다면 자동으로 개행이 출력된다
  • print( , end=””)를 이용하여 마지막 끝나는 문자를 지정해주면 한 줄로 출력이 가능하다.

💡 느낀점 or 기억할정보

• 문제 분석과 알고리즘 설계에 시간을 많이 투자하고 코드를 작성하니 더 빨리 코드를 작성할 수 있다. 알고리즘 설계를 꼼꼼하게 작성하고 코드를 짜도록 하자