21. 큐(10845) ,조세퍼스 문제(1158)

문제.
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다.
만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

답:

import sys

N = int(sys.stdin.readline().strip())

stack = []
for i in range(N):
  cmd = sys.stdin.readline().strip().split()
  if (cmd[0] == 'push'):
    stack.append(cmd[1])
  elif (cmd[0] == 'pop'):
    if (len(stack) != 0):
      print(stack.pop(0))
    else:
      print(-1)
  elif (cmd[0] == 'size'):
    print(len(stack))
  elif (cmd[0] == 'empty'):
    if (len(stack) == 0):
      print(1)
    else:
      print(0)
  elif (cmd[0] == 'front'):
    if (len(stack) != 0):
      print(stack[0])
    else:
      print(-1)
  elif (cmd[0] == 'back'):
    if (len(stack) != 0):
      print(stack[-1])
    else:
      print(-1)

큐의 특징은 선입선출. 즉 먼저 들어온 것은 먼저 나가는 특성을 가지고 있다.

어차피 파이썬에서 리스트를 구현하면 어디에서 인덱스를 뺄 것이냐에 따라 큐가 될 수도, 스택이 될 수도 있게 상황에 맞게 구현하면 된다.

배열의 인덱스에서 마지막은 -1로 말할 수 있고, 처음은 0이라고 표기가 가능하기에 이런 부분을 이용해서 구현하면 된다. 구현은 문제에서 제시한 것 그대로 경우의 수를 나누어 구현하면 된다.

(참고로 strip함수는 문자열 및 공백을 제거해 주는 함수이다.)

---

문제.

요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

답:

N,K = map(int,input().split())
arr = [i for i in range(1,N+1)]    # 맨 처음에 원에 앉아있는 사람들

answer = []   # 제거된 사람들을 넣을 배열
num = 0  # 제거될 사람의 인덱스 번호

for t in range(N):
    num += K-1  
    if num >= len(arr):   # 한바퀴를 돌고 그다음으로 돌아올때를 대비해 값을 나머지로 바꿈  
        num = num%len(arr)
 
    answer.append(str(arr.pop(num)))
print("<",", ".join(answer)[:],">", sep='')

arr라는 배열에 1부터 n까지의 (정수대로) 일렬적으로 놓아둔 정수를 기입한다. 이건 원처럼 이루어져 있다고 상상해 볼 수 있다.

이후 사람들을 제거할 것인데, 이 부분을 answer라는 배열로 컨트롤하며, num을 이용해서 인덱스 번호를 컨트롤한다.

이후 for문과 if문을 이용하여 계산을 이루어지게 한다. 

제거는 숫자가 오름차순되게 이루어지고, 제거는 한 바퀴를 돌고 다시 제거해야 한다.

이때 인덱스와 전체 배열을 이용해서 나머지를 구해야 한다. (배열의 길이로 나눠야 하니 len함수를 써야 함.)

모든 for문이 끝나면 arr에 num가 정렬이 될 것이고, 이후 pop을 이용해서 제거한다.

이후 다시 str 강제 형변환을 하고 빈 배열인 answer에 넣어준다.

그다음 "< >"을 프린트해줘야 해서 join함수와 sep함수를 이용해서 프린트해 준다.

(sep은 구분자를 넣어주는 함수이다.) - (여기에 구분자는 공백이 되어줄 것.)

결론

c언어에서는 어떻게 코드를 구현하는 건지 궁금해진다.

(파이썬으로 문제를 풀기 잘한 거 같다...)