백준 21939 문제 추천 시스템 Version 1 (python)

문제 URL : https://www.acmicpc.net/problem/21939

 

문제접근법 : 

 

문제 번호와 ,문제별 난이도가 있을때 가장 어려운 문제 ,혹은 가장 쉬운문제의 번호를 출력하는 문제입니다.

 

가장 어려운 문제, 가장쉬운문제 떠오르는게 바로 생각나죠?

가장큰값 가장작은값 빠르게 출력하는 자료구조 우선순위 큐겠죠?

 

maxheap 과 minheap을 동시에 사용을해야하기때문에 map을 이용해서 해당 데이터를 삭제처리 했는지 확인하기위해 map도 필요합니다.

해당 조건을 그대로 시뮬레이션 구현하는 문제고 

주의할점은 recommend가 나올때 당연히 데이터가 삭제되는줄 알았다. 삭제가아닌 출력입니다.

삭제하시면안되요 단->(이미 삭제된 데이터는 heap에 남아있을때 삭제해도 상관없습니다.)

 

 

오랜만에 푸는 문제라 파이썬으로 풀어봤습니다.

 

 

소스코드 : 

import heapq
from collections import Counter
import sys
#sys.stdin = open('input.txt')
input= sys.stdin.readline

n = int(input())
minpq = []
maxpq = []
c = Counter()
def add(a,b):
    global minpq,maxpq,c
    heapq.heappush(minpq,(b,a))
    heapq.heappush(maxpq,(-b,-a))
    c[a]=b
def recommend(a):
    global minpq,maxpq,c
    
    if a==1:
        while True:
            l,p = maxpq[0]
            l = -l
            p= -p
            if c[p]!=l:
                heapq.heappop(maxpq)
                continue
            return p
    else:
        while True:
            l,p = minpq[0]
            if c[p]!=l:
                heapq.heappop(minpq)
                continue            
            return p
            
def solved(p):
    global c
    c[p]=0
        
for i in range(n):
    a,b = map(int,input().split())
    add(a,b)
    
m = int(input())

for i in range(m):
    s= input().split()
    if s[0] == 'add':
        add(int(s[1]),int(s[2]))
    elif s[0]=='recommend':
        print(recommend(int(s[1])))
    else:
        solved(int(s[1]))

 

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.