#13. 백준 1158번 (python)

 

자료구조를 공부하나가 만난 문제이다. 아주 고전적인 문제라고 하는데 난 왜 어렵나..

 

이거 실버 4인데 아니다 이거 체감상 실버 2는 되는 듯.. 아니면 내가 못 하는 건가.... 하하하

 

스택만 풀다가 이 문제도 스택으로 해보려 했는데 안 된다...

 

알아보니 이건 큐로 푸는 거였다... 큐가 뭐지 까먹었다.. 다시 공부한다.;

 

 

큐(Queue)란?

" 쉽게 말해 줄 서기"  

 

• 선입선출(First In, First Out, FIFO) 구조.
• 먼저 들어온 데이터가 먼저 나간다.

기본 동작

enqueue : 데이터를 큐에 넣는다 (ex: 손님 줄 서기)

dequeu : 데이터를 큐에서 빼기 (ex: 맨 앞 손님 퇴장)

 

 

기본 용어

Front : 큐에서 가장 먼저 나갈 데이터의 위치.
예: 줄 맨 앞 사람.

Rear (또는 Back) : 큐에서 가장 마지막에 들어온 데이터의 위치.
예: 줄 맨 뒤 사람.

Empty : 큐에 아무 데이터도 없는 상태.

Overflow : 큐가 꽉 차서 더 이상 데이터를 넣을 수 없는 상태.

Underflow : 큐가 비어 있는데 데이터를 꺼내려고 해서 에러가 나는 상태.

Circular Queue : 끝까지 가면 다시 처음으로 돌아가는 구조의 큐.

Priority Queue : 우선순위가 높은 데이터가 먼저 나가는 큐. FIFO가 아님.

Deque (Double-ended Queue) : 앞뒤 양쪽 모두에서 데이터를 넣고 뺄 수 있는 큐

 

 

본 문제는 원형 큐가 사용되었다. 원형 큐가 있는 걸 처음 안 나다 하하핳

 

정답 

import sys

def Josephus(queue, K):
    result = list()
    num = K - 1
    for i in range(len(queue)):
        if (len(queue)>num):
            result.append(queue.pop(num))
            num += K - 1
        elif (len(queue) <= num):
            num = num%len(queue)
            result.append(queue.pop(num%len(queue)))
            num += K - 1
    return result

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    queue = list()
    for i in range(1, N + 1):
        queue.append(i)
    result = Josephus(queue, K)
    print('<', end='')
    for i in range(N):
        if (i != N -1):
            print(f'{result[i]}, ', end="")
        else:
            print(f'{result[i]}', end="")
    print('>', end="")

사실 열심히 풀어봤는데 시간이 너무 많이 흘러 그냥 정답을 봤다... 흑흑

 

포인트는 내가 생각하기에 (queue) <= num 일때 처리 방법, __name__, 출력형식 정도..?

 

너무 너무 나에겐 어려움,.... 지금은 사실 모두 이해한 건 아니라서 나중에 다시 보려고 초스팅한다. 흑ㄷ흑 이거 푸는 사람 대단한 사람