[Section05] Python 알고리즘 문제풀이 05~06

Q5. 공주 구하기(큐) : N명의 왕자 중에서 K번째 왕자를 반복 제거하고 최종적으로 남는 왕자를 출력

입력 : 

N(5<=N<=1,000) K(2<=K<=9)

출력 : 왕자 번호

 

[내가 쓴 코드]

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

a = deque(range(1, n + 1))

while len(a) != 1 :
    a.rotate(-k+1)  #음수로 회전 방향을 왼쪽으로 줌
    a.popleft()    

print(*a)

 

[풀이 코드]

n, k = map(int, input().split())
dq = deque(range(1, n + 1))

#강의 앞부분 듣고 rotate 없이 작성해봄
count = 1

while len(dq) != 1 :
    b = dq.popleft()
    if count == k :
        count = 1
    else :
        dq.append(b)
        count += 1
        
print(b[0])
       
#풀이코드
while dq :
    for _ in range(k-1) :
        cur = dq.popleft()
        dq.append(cur)
    dq.popleft()
    if len(dq) == 1 :
        print(dq[0])
        dq.popleft()

 

 

 

---

Q6. 응급실 : N명의 환자가 대기하고 있을 때 진료를 받는 사람보다 위험도가 높은 사람이 뒤에 존재하면 현재 환자는 맨 뒤로 감. 이를 반복하여 M번째 환자가 진료받는 순서를 출력

입력 : 

N(5<=N<=100) M(0<=M<N)

출력 : M번째 환자 진료 순서

 

[내가 쓴 코드]

n, m = map(int, input().split())
a = deque(map(int, input().split()))

count = 0

while True :
    b = a.popleft()  #첫번째 환자를 꺼냄
    for i in range (len(a)) :
        if b < a[i] :  #대기 환자 중에서 위험도가 높은 환자가 존재하면
            a.append(b)  #맨뒤로 넣음
            if m == 0 :  #뒤로 간 환자가 m번째 환자면
                m = len(a)-1  #m의 index 변경
            else :
                m -= 1  #아니면 줄을 한칸씩 앞으로
            break
    else :  #대기 환자 중 위험도가 높은 환자가 없으면
        count += 1  #치료 환자 증가
        if m == 0 :  #방금 치료한 환자가 m번째 환자면
            break  #모든 반복 종료
        m -= 1  #아니면 줄을 한칸씩 앞으로
        
print(count)

 

[풀이 코드]

n, m = map(int, input().split())
Q = [(pos, val) for pos, val in enumerate(list(map(int, input().split())))]
#index(pos)와 위험도(val)가 같이 저장되는 tuple로 저장

Q = deque(Q)  #queue로 변경

cnt = 0

while True :
    cur = Q.popleft()
    if any(cur[1] < x[1] for x in Q) :  #현재 환자의 위험도보다 높은 환자가 대기열에 있는지 확인
        Q.append(cur)
    else :
        cnt += 1
        if cur[0] == m :
            break
            
print(cur)

튜플을 생각하긴 했는데 단순 index를 저장하기엔 좀 아깝다고(?) 생각이 들어서 m을 조작하는 걸로 풀었음

튜플로 하니까 훨씬 간결하네,,,