스택, 큐, 덱 (2)

2164번 

 

카드2

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초 (추가 시간 없음)

128 MB

142020

73951

57429

50.972%

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1 복사

6

예제 출력 1 복사

4

 

초기 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
queue= deque()

for i in range(n):
    queue.append(i)
a = queue.popleft()
queue.append(a)      #2제일아래로 옮기기 
queue.popleft()      #3버리기 
b = queue.popleft()  #4를 빼고 저장해서
queue.append(b)      #뒤에 저장하기 
queue.popleft()  
print(queue)

 

출력초과가 나옴

popleft()과 append()를 반복해 단 하나의 원소가 남을 때까지 반복하면 되는데, 이를 함수로 구현할 수 있음

 

정답 코드

from collections import deque

def last_card(n):
    queue = deque(range(1, n+1))
    while len(queue) > 1:
        queue.popleft()
        queue.append(queue.popleft())
    return queue[0]

n = int(input())

print(last_card(n))

아직 함수가 익숙하지 않은 것 같음 

 

백준 모의고사 

[PCCE 모의고사] 4번

darklight

sublimevimemacs

Python3 

문제 설명

영진이는 수를 거꾸로 세는 연습을 하고 있습니다. 단순히 5, 4, 3, 2, 1처럼 시작하는 수인 5부터 끝나는 수인 1까지 1씩 감소하는 게 아닌 감소하는 간격과 끝나는 수도 자유자재로 조절하며 수를 세고 싶습니다. 단, 수를 셀 때는 끝나는 수보다 더 작아지지는 않도록 해야합니다.

예를 들어 10부터 2씩 감소하며 3에서 끝나도록 수를 세면 다음과 같습니다.

10
8
6
4

4에서 2가 더 감소하면 2가 되지만 끝나는 수보다 작기 때문에 4까지만 수를 셉니다.

주어진 코드는 시작하는 수 start, 간격 step, 끝나는 수 end가 정수 입력으로 주어질 때, start부터 end까지 step만큼 감소하는 수들을 한 줄에 한 개씩 출력하는 코드입니다. 올바르게 작동하도록 한 줄을 수정해주세요.

---

제한사항

• 10 ≤ start ≤ 50
• 1 ≤ step ≤ 10
• -50 ≤ end < start

---

입출력 예

입력 #1

10
2
3

출력 #1

10
8
6
4

입력 #2

10
3
1

출력 #2

10
7
4
1

입출력 예 설명

입출력 예 #1

• 본문과 동일합니다.

입출력 예 #2

• 10부터 1까지 3씩 감소하도록 수를 세면 10, 7, 4, 1이 됩니다.

start = int(input())
step = int(input())
end = int(input())

for i in range(end, step, start):
    print(i)

 

오류 정정 
for i in range(end, step, start): --> for i in range(start, end-1, step):

쉬운것도 바로 찾지 못해서 큰일이다.. 

 

11866번

 

요세푸스 문제 0

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

91225

52063

43616

56.687%

문제

요세푸스 문제는 다음과 같다.

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 ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1 복사

7 3

예제 출력 1 복사

<3, 6, 2, 7, 5, 1, 4>

 

3번째 자리가 지워지면, 지워진 다음숫자부터 시작해 또 다시 3번째 숫자를 카운트 하고 지우고 지운숫자를 출력해야 함 

작동로직은 이해했는데, 코드 구현이

import sys 
n, k =  map(int, sys.stdin.readline().split()) 
def pus(n):
    queue = daque(range(1, n+1))
    
    while len(queue) > 1 :
        queue.remove(queue[2])
    return queue.remove(queue[2])

지워진 다음숫자부터 시작해 또 다시 3번째 숫자를 카운트한다 부분을 코드로 어떻게 구현할지 막혔음

deque로 원형 q를 구현한다는 사실을 인지하지 않음

from collections import deque
import sys

n, k = map(int, sys.stdin.readline().split())

def josephus(n, k):
    queue = deque(range(1, n+1))
    result = []
    
    while queue:
        # k-1번 회전 (k번째 요소가 맨 앞에 오도록)
        for _ in range(k-1):
            queue.append(queue.popleft()) #1을떼서1을끝에다가반환,2를떼서2를끝에다가반환
        
        # k번째 요소 제거 및 결과에 추가
        result.append(str(queue.popleft()))
    
    return "<" + ", ".join(result) + ">"

print(josephus(n, k))

join()은 리스트의 모든 요소를 하나의 문자열로 반환