[백준] 11866 요세푸스 문제 0 (Baekjoon Problem 11866: Josephus problem 0)

문제 출처

 

[문제 요약]

원형 테이블에 n명의 사람들이 순서대로 앉아있다.

양의 정수 k가 주어지면 k번째에 앉은 사람을 제거하고, 재거한 사람 이후부터 다시 k번째에 앉아있는 사람을 제거한다.

이와 같은 방식으로 모두를 제거할때 제거하는 순서를 적으면 된다.

 

입력은 n k로 주어진다.

 

예를들어 입력이 7 3이라고 하자.

그리고 어떤 사람을 지울지 가리키는 변수를 편의상 idx(index 인덱스)라고 정의했다.

총 7명의 사람들이 원형으로 앉아있고, 스탭(step)은 3이어서 idx는 3씩 더해진다.

움직이는 칸을 편의상 스탭이라고 불렀다.

 

위 그림과 같은 상황에서 1부터 3칸을 세어보자.

그러면 처음으로 제거되는 숫자는 3이다.

제거된 수 이후부터 3칸을 더 가면 6,

또 3칸을 세어 원형 테이블의 마지막 사람 이후에 처음 사람부터 남은 스탭을 세면 2,

없는 사람을 제외하고 또 3칸을 더가면 7 순으로 아래의 표처럼 순서가 완성된다.

출력은 <>안에 괄호로 구분된 순서가 프린트 되어야한다.

ex) <3, 6, 2, 7, 5, 1, 4>

[풀이]

처음에 circle queue나 linked list를 사용할까 하다 굳이 한칸씩 이동할 필요가 있을까 싶어서

리스트에서 사람(숫자)를 하나씩 지우고 리스트가 비워질때까지 룹(loop)을 돌리는 방법으로 했다.

 

1부터 n까지의 원형 테이블 리스트(이름: lst)와

결과를 넣을 리스트(이름: res) 2개를 만들어주고,

idx = -1로 설정해둔다 (index는 0부터 시작하기 때문)

 

(while loop안에서)

우선 idx에 k를 더한다.

만약 lst의 index보다 idx가 크면 lst의 길이로 나눈 나머지가 idx가 된다.

그리고 해당 변수를 res에 넣어준다.

방문한 변수는 lst에서 빼줌

idx를 1 빼줌 (유의할점 참고)

[유의할 점]

• 리스트 끝에 다다랐을때 n으로 나눴었는데 out of index error납니다 (당연한게 리스트 사이즈가 줄어드니 ㅜ)
• del elem을 하면 리스트 사이즈가 줄어들기 때문에 idx도 하나 빼주어야한다. 물론 애초에 k-1을 더해줘도 된다.
• res에 넣을때 string(문자)로 타입변환을 해주면서 넣어준다. 그래야 하단의 join 사용 가능함.

[파이썬 3 코드]

# -*- coding: utf-8 -*-

if __name__ == "__main__":
    n, k = map(int, input().split())

    lst = [i for i in range(1, n+1)]
    res = []

    idx = -1
    while len(lst) != 0:
        idx += k
        if idx >= len(lst):
            idx %= len(lst)
        res.append(str(lst[idx]))
        del lst[idx]
        idx -= 1

    print("<{}>".format(", ".join(res)))