[알고리즘] 7일차 (카드 게임, 절댓값 힙 구현하기) #백준2164번 #백준11286번

클라우드·2023년 9월 23일

목록 보기

7/35

📌 문제 013) 카드 게임

시간 제한 2초, 실버 IV, 백준 2164번

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
6 # 카드의 개수

출력

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

1단계 문제 분석

popleft를 수행하여 맨 앞의 카드를 버린다.
위 과정에 이어 바로 popleft -> append를 수행해 맨 앞에 있는 카드를 가장 아래로 옮긴다.
큐의 크기가 1이 될 때까지 위 과정을 반복한 후, 큐에 남은 원소를 출력한다.

2단계 슈도 코드

N(카드의 개수) myQueue(카드 저장 자료구조)

for 카드의 개수만큼 반복:
	큐에 카드 저장

while 카드가 1장 남을 때까지:
	맨 위의 카드를 버림: popleft()
    맨 위의 카드를 가장 아래의 카드 밑으로 이동: popleft() -> append()

마지막으로 남은 카드 출력

3단계 코드 구현

from collections import deque
N = int(input())
myQueue = deque()

for i in range(1, N+1):
    myQueue.append(i)

while len(myQueue) > 1: # 카드가 1장 남을 때까지
    myQueue.popleft() # 맨 위의 카드를 버림
    myQueue.append(myQueue.popleft()) # 맨 위의 카드를 가장 아래 카드 밑으로 이동

print(myQueue[0])

📌 문제 014) 절댓값 힙 구현하기

시간 제한 2초, 실버 I, 백준 11286번

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다.
18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
-1
1
0
-1
-1
1
1
-2
2
0

1단계 문제 분석

N의 최대 범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다.
데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 쉽게 해결할 수 있다.
단, 이 문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다.
x=0 일 때,
- 큐가 비어 있을 때는 0을 출력하고, 비어 있지 않을 때는 절댓값이 최소인 값을 출력한다. 단, 절댓값이 같다면 음수를 우선하여 출력한다.
x=1 일 때,
- put으로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬한다.

2단계 슈도 코드

N(질의 요청 개수)
우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설정
- 단, 절댓값이 같으면 음수 우선 정렬

for N만큼 반복:
	요청이 0일 때: 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front값 출력(get())
    요청이 1일 때: 새로운 데이터를 우선순위 큐에 더하기(put())

3단계 코드 구현

from queue import PriorityQueue
import sys
print = sys.stdout.write
input = sys.stdin.readline
N = int(input())
myQueue = PriorityQueue()

for i in range(N):
    request = int(input())
    if request == 0:
        if myQueue.empty():
            print('0\n')
        else:
            temp = myQueue.get()
            print(str((temp[1]))+'\n')
    else:
        # 절댓값을 기준으로 정렬하고 같으면 음수 우선 정렬하도록 구성
        myQueue.put((abs(request), request))