[알고리즘/구현] 11866번 : 요세푸스 문제 0 - python

링크 : https://www.acmicpc.net/problem/11866

 

 

 

 

 

 

---

• 문제
• 소요시간: 30분

---

• 설계하기(접근방법) 

1. 입력받기

n, k 를 입력받는다

 

2. 구현하기

이 순열의 구현 핵심은

줄어드는 배열을 어떻게 관리하느냐이다.

 

다른 사람의 풀이를 보니 큐로 쉽게 풀 수 있었다.

 

구현을 택한 나의 풀이이다

 

 

배열이 줄어들지 않도록

리스트에서 순서대로 제거한 

요세푸스 순열은 0으로 대체하였다

 

[1,2,3] -> [1,0,3]

 

요세푸스 숫자를 찾으려면

배열을 순회하면서

0이 아닌 숫자를 k번 만나면 된다

 

포인터를 1씩 증가시키면서

0이 아니면 check 라는 변수를 + 1 해준다

check가 k가 된다면 요세푸스 배열에 넣어준다

 

이 과정을 모든 원소가 0으로 바뀔 때까지 진행한다.

 

3. 출력하기

 

괄호에 주의하여 출력한다

 

---

• 코드(출력)

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

arr = [i for i in range(1, n + 1)]
ans = []

pnt = 0
cnt = n
check = 0

while cnt:
    if arr[pnt] == 0:
        pnt += 1
        pnt %= n
        continue
    else:
        if check == k - 1:
            ans.append(arr[pnt])
            arr[pnt] = 0
            cnt -= 1
            check = 0    
        else:
            check += 1
            pnt += 1
            pnt %= n


print('<', end='')
for i in range(n):
    if i == n - 1:
        print(ans[i], end = '')
    else:
        print(ans[i], end = ', ')    
print('>', end='')
-> print(f"<{', '.join(map(str, ans))}>")

---

• 얻어갈 부분

1. 마지막 출력할 부분

print(f"<{', '.join(map(str, ans))}>")
해당 형태로 join 연산자를 사용하면 깔끔해진다.