[백준] 1158 - 요세푸스 (with. Python)

💡문제 분석 요약

-- 문제 --

입력 : N, K(<=N)

• 1 부터 N 까지 원을 이룸

• 순서대로 K번째 사람을 제거

• N명의 사람이 모두 제거될 때까지 계속 진행

• 즉, 요세푸스 순열은 원에서 사람들이 제거되는 순서 (N, K)

💡알고리즘 설계

1. input을 통해 N, K 입력

2. 사람 리스트, 결과 리스트 생성

3. 사람들이 다 나갈 때 까지 반복문 생성 popleft로 사람 리스트에 넣어주고 인덱스 2번 자리 값은 결과 리스트로 넣어주기

💡코드

n, k = map(int, input())
people = [for i in range(1, n+1)]
result = []
while people:
    for u in range(k-1):
       people.append(people.popleft())
    result.append()

💡시간복잡도

O(N)

💡틀린 이유

1. 접근 방식 단순함.

2. 문제의 조건을 구현하는 능력이 떨어진다.

3. deque개념 부족

4. 문제 꼼꼼히 구현 안함.(사람들 넣어주는 과정 없음.)

💡틀린 부분 수정 or 다른 풀이

from collections import deque

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

# 1~n번 사람
people = deque()
for i in range(1, n+1): people.append(i)
result = []

while people:
  for _ in range(k-1):
    people.append(people.popleft())

  result.append(people.popleft())

print(str(result).replace('[', '<').replace(']', '>'))

💡느낀점 or 기억 할 정보

1. 처음 코테를 접하다보니 접근하는데 어려움을 느낌. -> 문제 많이 접해보기.

2. 개념만 공부하지 말고 기본 구현한 코드 많이 접해보기.

3. deque : 큐의 앞, 뒤에서 삽입, 삭제가 가능한 큐

   💡

   from collections import deque

4. map(int, input()) : 리스트의 각 요소를 정수(int)로 변환한다. 예를 들어, 리스트 ["5", "3"]의 각 요소를 정수로 변환하여 [5, 3]이라는 리스트를 만드는 것이다.

5. popleft() : 왼쪽 끝의 원소를 제거 후 반환한다.