백준(2164,11286)

카드게임(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. 패턴은 가장 위의 카드를 버리고, 그 다음 제일위에 카드를 반대쪽으로 보낸다. 이므로 Queue를 선언하여 해결한다.

2. 카드를 버리기전 Queue남은 값이 1개이면 그값을 출력해준다.

코드

from collections import deque
n = int(input())
card=deque([])
for i in range(n,0,-1):
    card.append(i)

while card:
    if(len(card)!=1):
        
        card.pop()
        t=card.pop()
        card.appendleft(t)
    else :
        print(card.pop())
        break

절댓값 힙 구현하기(11286)

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

• 입력

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

• 입출력 예시

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0
-------------------

-1
1
0
-1
-1
1
1
-2
2
0
# 입력의 0의 횟수만큼 출력을 한다.

해결책

1. 입력을 하나씩 받고, 그값이 0이아니면 min-heap에 대입한다.

   1.1 절댓값을 우선으로 heap을 생성하고, 하위조건으로 원래값의 대소를 이용한다.

2. 입력값이 0인경우 pop을 함으로써, 가장 절댓값이 작은값을 출력해주면된다.

   2.1 만일 heap이 empty한 경우에 0이 들어온다면 0을 출력해준다.

코드

import heapq
import math
import sys
from heapq import heappush, heappop

heap=[]
n = int(input())

for i in range(n):
    num = int(sys.stdin.readline())
    if num!=0:
        ab = abs(num)
        heappush(heap,(ab,num))
    else :
        if heap:
            print(heappop(heap)[1],end="\n")
        else :
            print("0",end="\n")