[백준] 조세퍼스 문제 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= "")
📌풀이
- 리스트에서는 0부터 시작이니까 -1해준다.
index += k - 1
- 살아있는 사람의 리스트인 person에서 인덱스에 해당하는 사람을 죽인다.
그 후 dead_person 리스트에 넣는다.
dead_person.append(person.pop(index))
- 이렇게 하다보면 리스트는 조세퍼스의 문제대로 원형이 아닌 일직선이기에 계산이 이어지지 않는다. 이어지게 하기 위해서 중간에 수식을 넣어준다.
1,2,(3),4,5,(6),7:죽은 사람
7부터 이어지도록 하는 것이 아니고 7의 값을 제하고 처음부터 시작하기 위해서 나머지를 구한다.
if index >= len(person):
index %= len(person)
Author And Source
이 문제에 관하여([백준] 조세퍼스 문제 1158번 파이썬 Python 자료구조), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tkdduf727/백준-조세퍼스-문제-1158번-파이썬-Python-자료구조저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)