[백준 / python] 1158번 : 요세푸스 문제

알고리즘 분류 자료구조 구현 큐

🔗 문제 출처 https://www.acmicpc.net/problem/1158

---

📎 코드

python

n,k = map(int,input().split())
li = [i+1 for i in range(n)]
result = []
idx = 0

for i in range(n):
  idx += k-1
  if idx >= len(li):
    idx = idx % len(li)
  result.append(li.pop(idx))

print('<',end='')
for i in result:
  if i == result[len(result)-1]:
    print(i,end='')
  else: print(i,',',sep='',end=' ')
print('>')

---

이 문제는 자료구조 카테고리에 있었지만 풀면서 개인적으로는 구현문제에 더 가까웠다고 생각한다. 큐의 특징을 가지고 있는 문제지만 파이썬의 특성상 리스트로 해결하였다.

위의 코드는 첫 번째 코드이다. 인덱스를 변수로 받아둔다. 만약 인덱스가 해당 배열의 길이를 넘는다면 다시 배열 앞으로 넘어가야하기 때문에 % 연산을 사용하였다.

보다시피 문제에서 요구하는 출력 형식을 맞추기 위한 부분이 상당히 지저분하다. 조금 더 깔끔하게 표현한 코드는 아래와 같다.

---

📎 개선코드

n,k = map(int,input().split())
li = [i+1 for i in range(n)]
result = []
idx = 0

for i in range(n):
  idx += k-1
  if idx >= len(li):
    idx = idx % len(li)
  result.append(str(li.pop(idx)))

print('<',', '.join(result),'>',sep='')

주의해야할 점은 join을 사용하기 위해선 배열의 요소가 int형이면 안된다는 것이다. 따라서 result 리스트에 담을 때 str형변환을 해주어야한다.