백준 1158

💡문제 분석 요약

• N명의 사람이 있고, K번째 사람을 제거한다. 제거되면 그 다음 K번째 사람을 다시 제거한다.
• 제거된 사람은 list에서 빠지게 된다.
• 최종 1명이 남을 때 까지 제거한다.

💡알고리즘 설계

• 원형큐를 사용해야될 것 처럼 보였는데, 일단은 list를 사용한 큐로 풀었다.
• 나머지 계산이 들어갈 것으로 보이고, len(list)를 나누는 것을 pop하고 나서 할지, 이전에 할지 생각해보면 될 것 같다.

💡코드

n, k = map(int, input().split())
lst = [x+1 for x in range(n)]

removed_people = [] # 제거된 사람 모임
remv = 0 # 제거될 사람

for i in range(1, n+1):
    remv += (k-1)
    if remv >= len(lst):
        remv %= len(lst)
    removed_people.append(lst[remv])
    lst.pop(remv)

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

💡시간복잡도

• N명의 사람에 대해 for문을 돌리고, 그 안에서는 if 외에 별다른 조건이 없으므로 O(N)이 될 것으로 예상된다.

💡 틀린 이유

• pop을 어디서 해야하는지 헷갈렸다. 처음부터 나머지 계산으로 풀어야겠다고 생각은 했는데 이를 pop 해주고 해야하는지, pop하기 전에 해야하는지 헷갈렸다.
• 또한 if로 비교할 때 등호를 안써서 틀렸다. 시작이 0이기 때문에 등호를 붙여야 했는데 이를 빼먹었다.
• 최종 답안 표기 하는 방법을 몰라서 틀렸다. 이는 인터넷을 찾아 join으로 풀었는데, 처음에는 하나하나 for문으로 출력했는데 너무 코드가 이상해져서 인터넷을 참고하여 작성하였다.

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

• while을 사용하여 len가 0보다 클때까지 지속한 풀이도 가능했다.

💡 느낀점 or 기억할정보

• join 사용법 익히기
• 비교할 때 항상 등호가 들어가는지 안들어가는지 생각해본 후 해야한다.