[알고리즘/Python] BOJ 1158 - 요세푸스 문제 (기초 자료구조)

BOJ 문제페이지

원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

 

풀이1

• 단순히 리스트를 사용해서 풀었다.
• index와 target 변수를 지정해 리스트에서 target 을 제거하고,
• 다시 현재위치에서 k번째 사람이 제거될수 있도록 index 를 변경시켰다.

# BOJ-1158.py

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
nums = list(range(1, n+1))
result = []
target = k
while(True):
    index = nums.index(target)
    nums.remove(target)
    result.append(target)

    if not nums:
        break

    index += k - 1
    if index >= len(nums):
        index = index % len(nums)
    #print(target, "->", nums[index])
    target = nums[index]

print("<{}>".format(", ".join(map(str, result))))

 

 

풀이 2

• index 와 target 은 같은 의미이므로 target 변수를 삭제했다.
• 코드가 더욱 간결해짐!

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
nums = list(range(1, n+1))
index = k - 1
result = []
while(True):
    result.append(nums.pop(index))
    if not nums:
        break
    index += k - 1
    if index >= len(nums):
        index = index % len(nums)

print("<{}>".format(", ".join(map(str, result))))

 

 

풀이3

• 풀이2와 메모리, 시간은 똑같음
• index 나누기 연산을 굳이 if 문으로 확인하지 않고 사용해도 된다.
  • 연산 순서를 바꿔야함
  • index 나누기 연산 → pop → index 이동
• 반복횟수는 n만큼 반복된다.
  • 풀이2에서의 While, if not 불 필요함.

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
nums = list(range(1, n+1))
index = k - 1
result = []
for _ in range(n):
    index = index % len(nums)    
    result.append(nums.pop(index))
    index += k - 1

print("<{}>".format(", ".join(map(str, result))))

---

BOJ 링크