[BOJ] 큐 문제 - 11866 요세푸스 문제 0, 1966 프린터 큐

11866 요세푸스 문제 0

생각 정리

1번부터 N번까지 N명의 사람이 앉아있음, K번째 사람을 순서대로 제거

원을 따라 계속해서 이 과정이 반복됨

원에서 사람들이 제거되는 순서를 N-K 요세푸스 순열 이라함

7, 3 요세푸스 순열은 3, 6, 2, 7, 5, 1, 4 이라함

N과 K가 주어지면 (N, K) 요세푸스 순열을 구하는 프로그램

⇒ 이게 3제거하고 다시 1,2,4여서 4제거하고 이런식이 아니라,

3을 제거하고 그뒤로 4,5,6이면 6이 3번째니 6을 제거하는 식

그리고 7,1,2가오니 2를 제거

1,2,3,4,5,6,7 KILL3

1,2,4,5,6,7 KILL 6

1,2,4,5,7 KILL 2

1,4,5,7 KILL 7

1,4,5 KILL 5

1,4 KILL 1

4 KILL 4

약간 이런 식이다 deque의 rotate를 사용해서 원하는 수보다 작을때마다 미리 회전시켜놓고 제일 앞에거를 popleft 해주는게 좋을 듯 싶다

풀이 코드 - 풀이만 맞음, 출력 미포함

from collections import deque
n, k = (map(int, input().split()))

yosep = deque()
yosep_answer = []

for i in range(1, n+1):
    yosep.append(i)

for j in range(n): #n번 연산을 반복해야함
    yosep.rotate(-k+1)
    if yosep:
        yosep_answer.append(yosep.popleft())
        #yosep.popleft()
        # yosep_answer.append(yosep.popleft())
    # print(yosep)
print(yosep_answer)

맞았는데 출력이

< 숫자, 숫자, 숫자 > 이렇게 나와야하는데 ㅋ

[ 숫자, 숫자, 숫자 ] 요로케 나왔다

리스트 대괄호 없애는 법 print(*arr) * 요고를 붙여준다

리스트 대괄호는 없애는데 쉼표는 붙여야 할때 print(*arr, sep=’,’) 이렇게

*print( yosep_answer,sep=', ' ) 이렇게 해주면되는데, 또 < > 이괄호도 넣어줘야함,,ㅋㅋ 아,,,

*print("<", end='') print( yosep_answer,sep=', ', end='' ) print(">")

일케 해주면 된다! end=’’ 이거는 띄어쓰기나 기호등을 넣으면 한줄로 출력해준다. 출력땜에 한참을 해맴 심지어 쉼표뒤에 띄어쓰기도 필수임;; 이거땜에 계속 제출했다. 초보자니 이런거 일일이 신경써서 출력법을 연습하지만,,,이것도 공부라고 위로중이다.

정답맞은 코드

from collections import deque
n, k = (map(int, input().split()))

yosep = deque()
yosep_answer = []

for i in range(1, n+1):
    yosep.append(i)

for j in range(n): #n번 연산을 반복해야함
    yosep.rotate(-k+1)
    if yosep:
        yosep_answer.append(yosep.popleft())
        #yosep.popleft()
        # yosep_answer.append(yosep.popleft())
    # print(yosep)
    
print("<", end='')
print( *yosep_answer,sep=', ', end='' )
print(">")

1966 프린터 큐

생각정리

큐의 숫자가

2 1 4 3

중요도가

A B C D 라면 C D A B 를 인쇄함 4→ 3 → 2→ 1 이런식

2 1 4 3 → 1 4 3 2 → 4 3 2 1

큐의 숫자가

1 1 9 1 1 1 이고, 0번째 숫자의 중요도의 출력순서는

1 1 9 1 1 1 → 1 9 1 1 1 1 → 9 1 1 1 1 1

5가 된다!

맨 앞의 숫자가 MAX 인지가 관건이다

즉, 맨 앞의 숫자가 MAX일 경우(더 이상 순서를 바꿀 필요가 없음!!), popleft() 해주고 카운트 +1, 인덱스 리스트는 하나씩 지워준다. 지워주다가 인덱스 리스트의 번호가 M과 같다면, 카운트를 print 해준다.

맨 앞의 숫자가 MAX가 아닐 경우(순서를 바꿔줘야 함!!), 가장 앞에 것을 맨 뒤로 보내준다

• 테스트 케이스 개수 n개
• 각 테스트 케이스마다의 문서 개수 N, 원하는 중요도 M
• 각 테스트 케이스의 문서 큐
• 문서의 인덱스를 담는 큐 (0 부터 n 까지)
• 문서의 출력 순서를 세기 위한 카운터 변수

풀이 코드

from collections import deque

n = int(input())
for i in range(n):
    N,M = map(int, input().split())
    L = deque(list(map(int, input().split())))
    idx = deque(list(range(N)))
    cnt = 0
    
    while L:
        if L[0] == max(L):
            cnt += 1
            L.popleft()
            
            pop_idx = idx.popleft()
            if pop_idx == M:
                print(cnt)
        else:
            L.append(L.popleft())
            idx.append(idx.popleft())