백준 21944 문제 추천 시스템 Version 2

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

 

문제접근법 : https://www.acmicpc.net/problem/21939의 문제의 확장버전 문제입니다.

이문제를 먼저 풀어보고 푸시는게 나을거에요

해당문제 글은 : https://congsoony.tistory.com/425

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

 

여기에 풀려있습니다.

 

이문제또한 heap과 map을 이용한 문제인데

힙6개를 이용해서 데이터 구분을 map으로 해주면 되는문제입니다.

그룹별은 해당 그룹별로 heap인덱스로 만들어주고

레벨별도 마찬가지로 heap을 만들어서 구분해주시면됩니다.

 

여기서 주의할점은 map에 데이터 판별할때 레벨과 그룹과 동시에 저장하셔야해요 처음에 레벨만 저장해도 될줄알았다가

틀리더라구요 레벨과 그룹을 동시에 저장하는게 가장 정확합니다.

 

소스코드 : 

import heapq
from collections import Counter,defaultdict

import sys
#sys.stdin = open('input.txt')
input= sys.stdin.readline

n = int(input())
minpq = []
maxpq = []
gminpq = defaultdict(list)
gmaxpq = defaultdict(list)
lminpq = defaultdict(list)
lmaxpq = defaultdict(list)
c = Counter()
def add(p,l,g):
    global minpq,maxpq,c,gminpq,gmaxpq,lminpq,lmaxpq
    heapq.heappush(minpq,(l,p,g))
    heapq.heappush(maxpq,(-l,-p,g))
    heapq.heappush(gminpq[g],(l,p,g))
    heapq.heappush(gmaxpq[g],(-l,-p,g))
    heapq.heappush(lminpq[l],(l,p,g))
    heapq.heappush(lmaxpq[l],(-l,-p,g))
    c[p]=(l,g)
def recommend(g,x):
    global minpq,maxpq,c,gminpq,gmaxpq,lminpq,lmaxpq
    if x==1:
        while True:
            l,p,g=gmaxpq[g][0]
            l = -l
            p = -p
            if c[p]!=(l,g):
                heapq.heappop(gmaxpq[g])
                continue
            return p
    else:
        while True:
            l,p,g = gminpq[g][0]
            if c[p]!=(l,g):
                heapq.heappop(gminpq[g])
                continue
            return p
        
def recommend2(x):
    global minpq,maxpq,c,gminpq,gmaxpq,lminpq,lmaxpq
    if x==1:
        while True:
            l,p,g = maxpq[0]
            l = -l
            p= -p
            if c[p]!=(l,g):
                heapq.heappop(maxpq)
                continue
            return p
    else:
        while True:
            l,p,g = minpq[0]
            if c[p]!=(l,g):
                heapq.heappop(minpq)
                continue
            return p
def recommend3(x,t):
    global minpq,maxpq,c,gminpq,gmaxpq,lminpq,lmaxpq
    if x==1:
        for i in range(t,101):
            while lminpq[i]:
                l,p,g = lminpq[i][0]
                if c[p]!=(l,g):
                    heapq.heappop(lminpq[i])
                    continue
                return p
    else :
        for i in range(t-1,0,-1):
            while lmaxpq[i]:
                l,p,g = lmaxpq[i][0]
                l=-l
                p=-p
                if c[p]!=(l,g):
                    heapq.heappop(lmaxpq[i])
                    continue
                return p
    return -1
def solved(p):
    global c
    c[p]=0
        
for i in range(n):
    x,y,z = map(int,input().split())
    add(x,y,z)
    
m = int(input())

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

 

 

 

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