[백준] 조세퍼스 문제 1158번 파이썬 Python 자료구조

📌문제 접근

살아있는 사람을 넣고 죽은 사람을 뺄 큐, 죽은 사람을 넣을 큐 이렇게 두 개의 큐를 사용한다.

내가 처음에 작성한 코드는 수식 없이 +1씩 카운팅해서 k와 같아질 때 죽이는 방식으로 했다.
카운팅으로만 코드를 짜니까 코드가 복잡해지고 길어졌다.

구글링 결과 수식으로 해결할 수 있었다.

📌내가 작성한 코드 (시간초과)

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

queue = list(range(1, n + 1))
death_queue = []
index = 0
count = 1

while n != len(death_queue):
    if index < n:
        index += 1
    else:
        index = 1

    if count != k:
        queue.append(queue[0])
        queue.pop(0)
        count += 1
    else:
        death_queue.append(queue[0])
        queue.pop(0)
        
        if not queue:
            break

        count = 1

print("<", ", ".join(map(str, death_queue)), ">", sep= "")

📌내가 작성한 코드 (정답)

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

person = list(range(1, n + 1))
dead_person = []
index = 0

for i in range(n):
    index += k - 1

    if index >= len(person):
        index %= len(person)

    dead_person.append(person.pop(index))
    
print("<", ", ".join(map(str, dead_person)), ">", sep= "")

📌풀이

1. 리스트에서는 0부터 시작이니까 -1해준다.

index += k - 1

2. 살아있는 사람의 리스트인 person에서 인덱스에 해당하는 사람을 죽인다.
   그 후 dead_person 리스트에 넣는다.

dead_person.append(person.pop(index))

3. 이렇게 하다보면 리스트는 조세퍼스의 문제대로 원형이 아닌 일직선이기에 계산이 이어지지 않는다. 이어지게 하기 위해서 중간에 수식을 넣어준다.
   1,2,(3),4,5,(6),7:죽은 사람
   7부터 이어지도록 하는 것이 아니고 7의 값을 제하고 처음부터 시작하기 위해서 나머지를 구한다.

if index >= len(person):
        index %= len(person)