백준 11866

링크

백준 11866

요세푸스 문제 0

---

문제를 보고 '원을 이루며 앉는다' 라는 문장 때문이었는지 작년 자료구조 수업시간에 배웠던 원형링크드리스트가 생각났다. 왠지 이걸 활용해서 풀면 될 것 같았다.
물론 생각이 난거지 저걸 제대로 구현해서 풀지는 못했다. (학교에서 알려줄 때 잘 배우자 😓)

대신 큐를 원형으로 구현해서 풀었다.
물론 파이썬에서 아직 큐를 어떻게 제대로 구현하는지는 모르지만
적어도 그 개념을 사용해서 풀었다고 생각한다.

input을 list에 담고
제거할 순서가 오기 전까지 dequeue와 enqeueu를 반복한다. (원형으로 요소들이 리스트 안에서 돌게끔)
그러다가 제거해야 하는 순서에 dequeue한 요소는 따로 저장해주었다.

---

오답 1

josephus = list(map(int, input().split()))
pick = josephus[1] - 1
circle = []
answer = []

for person in range(1, josephus[0]+1):
    circle.append(person)

while True:
    for i in range(pick):
        circle.append(circle.pop(0))
    answer.append(circle.pop(0))
    if len(circle) == 1:
        answer.append(circle.pop(0))
        break

print('<' + ', '.join(map(str, answer)) + '>')

해당 코드는 런타임 에러 (IndexError)가 나왔다.
일단 내 생각을 구현해 놓은 답 자체가 틀린것이 아니라는 것에 안도했다.
그러나 아무리 코드를 봐도 인덱스에러가 나올 부분이 보이지 않았다.
그래서 약간의 실수라도 발생할 여지를 줄이고자
while - break 가 아닌 while 조건문으로 바꿨다.

수정
입력을 1 1을 하게되면

        circle.append(circle.pop(0))
    answer.append(circle.pop(0))

위의 코드에서 원소가 빠져나가고
아래코드가 실행될 때 인덱스 에러가 발생한다.
IndexError: pop from empty list

따라서 인덱스 에러를 피하기 위해선 반복을 시작할 때 조건을 걸어줘야 한다.

---

정답 코드

josephus = list(map(int, input().split()))
pick = josephus[1] - 1
circle = []
answer = []

for person in range(1, josephus[0]+1):
    circle.append(person)

while len(circle) != 1:
    for i in range(pick):
        circle.append(circle.pop(0))
    answer.append(circle.pop(0))
answer.append(circle.pop(0))


print('<' + ', '.join(map(str, answer)) + '>')

오히려 코드가 더 간결해지고 런타임에러도 발생하지 않았다.
두 코드에서 내부적으로 어떤 차이가 있는지 궁금해졌다.

---

알게된 것👨‍💻

• 큐를 활용해서 리스트를 빙글빙글 돌아가게 만들 수 있다.
• 근데 이런식으로 하면 불필요한 반복이 너무 많이 생기는 것 같다.
  후에 원하는 요소만 뽑아내는 식으로 다시 풀어보고 싶다.
• while - break 보다 while 조건문이 에러발생 여지가 적은건가? 알아볼게 하나 더 생겼다.
• 조건문을 사용할 때 예외상황이 발생할 수 있음을 알고 코드를 짜자! 1 1을 입력하는 건 전혀 생각하지 못했다.