[Python] 백준 11866번 문제 풀이 - 요세푸스 문제 0

문제 링크

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

문제 이해

이 문제는 요새푸스 순열을 출력하면 되는 문제입니다.

만약에 (7,3) 요시푸스 순열이라면 <3,6,2,7,5,1,4>가 나오게 되는데요 어떤 과정을 거쳐서 나오게 되는거냐면

현재 인덱스에서 k-1을 더하고 전체 개수로 나머지 연산하여 인덱스를 구하고 그 수를 빼는 과정입니다.

idx = (idx +k-1) % length 라는 공식이 나옵니다.

인덱스는 0으로 시작합니다.

그리고 K는 3이니 K-1 = 2므로 각 연산마다 2를 더해줍니다.

• (1,2,3,4,5,6,7) -> 3
  • (0 + k-1)%7 해서 인덱스 2가 나오게 되고 인덱스 2번은 3이므로 3을 뺍니다.
• (1,2,4,5,6,7) -> 6
  • (2 + 3 - 1) % 6 → 4가 나오게 되고 인덱스 4는 6이므로 6을 뺍니다.
• (1,2,4,5,7) -> 2
  • (4 + 3 -1) % 5 → 1 이 나오게 되고 인덱스 1은 2이므로 2를 뺍니다.
• (1,4,5,7) -> 7
  • (1+3-1) % 4 → 3이 나오게 되고 인덱스 3은 7이므로 7을 뺍니다.
• (1,4,5) -> 5
• (1,4) -> 1
• (4) -> 4

나머지 3개의 연산도 다음 형식으로 진행되게 됩니다.

아이디어

위에 있던 공식을 사용해서 요세푸스 순열을 만들고 출력하면 됩니다.

아이디어를 정리하면

1. 인덱스를 idx = (idx + k -1) % length로 해서 최신화 합니다.
2. 배열에서 인덱스를 빼고 결과 배열에 저장합니다.
3. 출력 형식에 맞춰서 출력합니다.

시간복잡도

배열 길이만큼 반복하니 O(N)이 됩니다.

N은 1000이니 가능합니다.

코드 구현

이 아이디어를 처음에는 다음과 같이 remove를 사용해서 구현했었습니다.

n, k = map(int, input().split())

num_list = []
result = []
for i in range(1, n+1):
    num_list.append(i)

idx = 0
for _ in range(n):
    idx = (idx + k-1) % len(num_list)
    num = num_list[idx]
    num_list.remove(num)
    result.append(num)

print("<", end="")
print(", ".join(map(str, result)), end="")
print(">")

그러다가 pop을 사용해서 인덱스로 빼는 방법이 있다는 것을 알았고 그것을 사용하였고 길이 계산을 한번만 하는 코드로 수정하였습니다.

n, k = map(int, input().split())

num_list = []
result = []
for i in range(1, n+1):
    num_list.append(i)

idx = 0
length = len(num_list)
for _ in range(n):
    idx = (idx + k-1) % length
    result.append(num_list.pop(idx))
    length -= 1

print("<", end="")
print(", ".join(map(str, result)), end="")
print(">")

배운 점

배열 관련 메서드에 대해 학습하였습니다.

remove(item)를 사용하면 배열에서 특정 값을 제거할 수 있고

pop(idx)을 사용하면 배열에서 특정 인덱스를 제거할 수 있다는 것을 알았습니다.