[Baekjoon] 22252_정보 상인 호석

Gold V

문제(출처: https://www.acmicpc.net/problem/22252)

---

< 정보 상인 호석 >

 

문제 풀이 

 

HashMap과 우선순위 큐를 사용해서 문제를 해결했다.

 

이때 HashMap은 <이름, 우선순위 큐> 형태로 초기화하며, 우선순위 큐는 내림차순 순으로 우선순위를 뒀다.

1로 시작할 때는 key값으로 이름을 가지고 있는지 없는지 판단하여 정보를 저장해 주고,

2로 시작할 때는 정보의 개수에 따라 우선순위 큐에서 뽑아 더해준다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _22252_ { // 정보 상인 호석

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int q = Integer.parseInt(bf.readLine());

		HashMap<String, PriorityQueue<Integer>> map = new HashMap<>();

		long result=0;

		for (int i = 0; i < q; i++) {
			st=new StringTokenizer(bf.readLine());

			int cmd=Integer.parseInt(st.nextToken());
			String name=st.nextToken();
			int num=Integer.parseInt(st.nextToken());

			if(cmd==1) {
				if(!map.containsKey(name)) {
					PriorityQueue<Integer>queue=new PriorityQueue<>(Collections.reverseOrder());
					for(int j=0; j<num; j++) {
						queue.add(Integer.parseInt(st.nextToken()));
					}
					map.put(name, queue);

				}else {
					for(int j=0; j<num; j++) {
						map.get(name).add(Integer.parseInt(st.nextToken()));
					}
				}
			}else {
				if(map.containsKey(name)) {
					PriorityQueue<Integer>temp=map.get(name);
					int l= num>temp.size() ? temp.size() : num;
					for(int j=0; j<l; j++) {
						result+=temp.poll();
					}
				}
			}
		}
		System.out.println(result);
	}

}

 

Main

변수)
q : 쿼리의 개수
map : <고릴라 이름, 우선순위 큐 <정보>>
result : 정보 가치 총합
cmd : 1 or 2
name : 고릴라 이름
num : 정보의 개수
queue : 우선순위 큐 / 내림차순

 

-쿼리의 개수(q) 입력

- 쿼리의 개수만큼 쿼리 입력

: 1로 시작한다면 map에 key 값으로 고릴라의 이름이 있는지 없는지 확인 후 있으면 추가, 없으면 PriorityQueue 만들어서 추가

: 2로 시작한다면 구매하려는 정보의 개수가 queue의 size보다 큰지 확인 후 둘 중에 작은 값 개수만큼 뽑아서 result에 더해줌

- 정보 가치 총합(result) 출력

---

---