[알고리즘] - 22252. 정보 상인 호석

heyhey·2023년 2월 14일
0

알고리즘

목록 보기
8/9

문제

암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 사고파는 사람을 의미한다.

호석이는 아직 상인계의 새싹이기 때문에, 초기 투자를 통해서 여러 명의 "정보 고릴라"들로부터 정보를 모으려고 한다. 정보 고릴라란 여기저기서 정보를 수집하는 사람들을 의미한다. 일단 정보를 긁어모으기 위해서 호석이는 여러 정보 고릴라들에게 정보를 구매하려고 한다.

암흑가의 연락망은 빼곡하기 때문에 누가 어떤 정보를 얻었는지에 대한 찌라시들이 수시로 퍼진다. 찌라시로 알 수 있는 것은, 어떤 이름을 가진 고릴라가
C1C_1,
C2C_2, ...,
CkC_k 만큼의 가치가 있는 정보 k 개를 얻었다는 점이다.

호석이는 이를 바탕으로 임의의 시점에 특정 고릴라에게 정보를 몇 개 살 것인지를 정할 수 있다. 이때 가치 순으로 가장 비싼 정보들을 구매한다. 예를 들어 고릴라가 가진 정보가 10개이고, 호석이가 사고 싶은 정보 개수가 4개라면, 고릴라는 10개 중에서 가치 순으로 가장 비싼 4개를 팔 것이다. 한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다.

당신은 암흑가의 주먹이며 양대 산맥이 될 가능성이 있는 호석이를 주시하고 있다. 관찰하면서 얻은 정보는 총
QQ 개이다. 각 정보는 다음의 2가지 중 하나이다.

1 Name
kk
C1,C2,...,CkC_1, C_2, ..., C_k : 이름이 [Name]인 고릴라가
kk 개의 정보를 얻었으며, 각 가치는
C1C_1 부터
CkC_k 이다.
2 Name
bb : 호석이가 이름이 [Name]인 고릴라에게
bb 개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼
bb 개를 구매하며, 고릴라가 가진 정보가
bb개 이하이면 가진 모든 정보를 구매한다.
견제를 위해서 호석이가 가진 정보들의 가치 총합, 즉 호석이가 정보들을 구매하는 데에 쓴 돈의 총합을 구하자.

풀이

입력의 형태이다
1 / Cpp / 5 / [10 4 2 8 4] : 입력 , 이름 , 개수 , 리스트내용
2 Cpp 2 : 출력 ,이름 ,개수

보자마자 Object 에 key와 리스트로 된 value를 통해 입력을 받으면 될 것 같다고 생각했다. 그리고 최대 값을 뽑아낼건데, 매번 정렬을 해주는 것 보다 heapq를 이용해서 입력을 받을 때 정렬을 해주는것이 좋을 것 같았다


T = int(input())
dict = {}
result = 0

def _heappush (heap,items):
  for item in items:
    heapq.heappush(heap,int(item)*-1)

for _ in range(T):
  input_list = list(input().split())
  TYPE,PERSON,COUNT = input_list[0],input_list[1],int(input_list[2])
  
  input_list = input_list[3:]

  if TYPE=="1":
    tmp = []
    if PERSON in dict.keys():
      tmp = dict[PERSON]
    _heappush(tmp,input_list)
    dict[PERSON] = tmp  
  elif TYPE=="2":
    for _ in range(COUNT):
      try:
        result += heapq.heappop(dict[PERSON])*-1
      except:
        # pass ... 와씨 ......
        break
        

print(result)

처음에 except 에 pass를 썼는데, 없는 항목일지라도 끝까지 순회를 해서 시간초과가 났었다... => Break 로 변경 후 통과 (7회)

profile
주경야독

0개의 댓글