백준(BAEKJOON) 1158 요세푸스 - 파이썬(python)

 

처음에는 list로 접근하여 index를 1씩 더해주고 k보다 커지면 %연산을 해서 다시 활용하는 방식을 생각했었는데 구현하지 못했고, deque도 비슷한 맥락에서 풀지 못했었음

원형으로 되어 있는 것이 아니기 때문에 처음엔 좀 헷갈렷었음

 

1 2 3 4 5 6 7

pop: 3
남은 큐: 4 5 6 7 1 2

pop: 3, 6
남은 큐: 7 1 2 4 5

pop: 3, 6, 2
남은 큐: 4 5 7 1

pop: 3, 6, 2, 7
남은 큐: 1 4 5

pop: 3, 6, 2, 7, 5
남은 큐: 1 4

이런 식으로 k번째 숫자는 삭제되고 그 이전까지 순회하던 숫자들은 큐의 마지막으로 이동시키는 방법으로 원형 리스트를 구현

 

from collections import deque
n, k = map(int, input().split())

q = deque(range(1, n+1))
answer = []
while len(q) != 1:
    for _ in range(k-1):
        q.append(q.popleft())
    answer.append(q.popleft())
answer.append(q[0])

print(f"<{', '.join(map(str,answer))}>")

정답을 출력하는 과정에서 print문의 sep=''를 이용하기도 했지만 f-string으로 하는 것이 더 간결한 것 같음

# print("<", ", ".join(answer), ">", sep="")
# 출력부분에 있어서 앞뒤로 <> 기호를 붙여야 하기 때문에 프린트문 내부에 넣어두고,
# 그 사이에 결과 리스트를 ", "로 join하여 프린트함.
# sep="" 인자는 "<" - ", ".join(answer) - ">" 세 개를 프린트할 때 구분자를 ""로 하겠다는 의미이기 때문에 필요
# 그렇지 않으면 < 3, 6, 2, 7, 5, 1, 4 > 의 결과물이 출력됨.

정답을 맞추기는 하였지만 list로 푸는 사람들도 많았고 현재 코드는 실행 시간이 너무 오래걸린다는 단점이 있어 조금 더 고민해봐야 할 것 같음

메모리도 그렇고 실행시간도 그렇고 list로 푸는 풀이가 더 효율적인 것인지, 작성한 코드가 잘못된 부분이 있는 것인지 잘 모르겠음