Level 3-2 ( 1)이중우선순위큐 2)야근 지수 )
### 2022.10.26. 수
1) 이중우선순위큐 (60%)
① 사용 알고리즘 : 이중 우선순위 큐
② 참고 링크
- 우선순위 큐 직접 구현
https://hongjw1938.tistory.com/22
자료구조 - 우선순위 큐(Heap, Priority Queue)
1. 우선순위 큐(Priority Queue)란? 이 자료구조는 우선순위 큐라는 말에서 볼 수 있다시피 우선순위가 높은 것을 먼저 꺼내기 위하여 만들어진 자료구조이며, 힙(Heap)이라고도 부른다. 예를 들어서,
hongjw1938.tistory.com
- java 우선순위 큐
https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90
[Java] Priority Queue(우선 순위 큐)
PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터
velog.io
- java 우선순위 큐 string
https://eno1993.tistory.com/127
JAVA Priority Queue 우선순위 큐 사용법과 정렬 기준 정의
기본적으로 Integer 값 혹은 String 같은 타입을 담는 우선순위 큐는 아래와 같은 방식으로 사용하면 된다. import java.util.*; // Priority_Queue 오름차순 정의 PriorityQueue priorityQueueAsc = new PriorityQueue(); // Prio
eno1993.tistory.com
③ 코드
↓↓↓ 코드 복.붙
import java.util.*;
//import java.util.LinkedList;
//import java.util.Queue;
class Solution {
public int[] solution(String[] operations) {
// 1. 우선순위 큐 선언
// Priority_Queue 오름차순 정의 (priorityQueueAsc)
PriorityQueue<Integer> pqAsc = new PriorityQueue<Integer>();
// Priority_Queue 내림차순 정의 (priorityQueueDes)
PriorityQueue<Integer> pqDes = new PriorityQueue<Integer>(Collections.reverseOrder());
System.out.println("1.len:::"+operations.length);
System.out.println("2.oper:::"+Arrays.toString(operations));
// 2. 우선순위 큐에 배열 삽입
for(String oper : operations){
//System.out.println("3.oper:::" + oper);
String opt = oper.split(" ")[0];
String val = oper.split(" ")[1];
switch(opt){
case "I":
pqAsc.offer(Integer.parseInt(val));
pqDes.offer(Integer.parseInt(val));
break;
case "D":
if("1".equals(val)){
// 최댓값 삭제
if(!pqDes.isEmpty()){
int elm = pqDes.poll();
pqAsc.remove(elm);
}
}else if("-1".equals(val)){
// 최솟값 삭제
if(!pqDes.isEmpty()){
int elm = pqAsc.poll();
pqDes.remove(elm);
}
}
break;
}
}
/* 전체 출력 */
/*
System.out.println("[최소큐]");
while(!pqAsc.isEmpty()) {
System.out.println(pqAsc.poll());
}
Iterator iter = pqAsc.iterator();
while(iter.hasNext()) {
System.out.println(iter.next());
}
*/
/*
System.out.println("[최대큐]");
while(!pqDes.isEmpty()) {
System.out.println(pqDes.poll());
}
*/
int[] answer = {0,0};
if(pqAsc.size() > 0){
answer[0] = pqDes.poll();
answer[1] = pqAsc.poll();
}
return answer;
}
}
2) 야근지수 (57%)
① 사용 알고리즘 : 이중 우선순위 큐
② 코드
c++
↓↓↓ 코드 복.붙
#include <string>
#include <vector>
#include <queue>
using namespace std;
/*
야근지수가 제곱을 하기 때문에 최대 값에서 -1을 해주는 것이 항상 최소값을 가진다.
a, b, c, ... 가 있을 때
a > b > c , ... 라고 가정하면
n = 0일때 야근지수는 a^2 + b^2 + c^2 + ... (A라 하자)이다.
야근 지수를 최대값에서 뺏을 때와 그 이전에서 뺏을 때를 비교 해보면
* 0. a^2 + b^2 + c^2 + ... => A
1. (a-1)^2 + b^2 + c^2 + ...
2. a^2 + b^2 + (c-1)^2 + ...
식 1. => A + -2a + 1
식 2. => A + -2c + 1
로 변환할 수 있다.
여기서 a > c이고 정수 임으로
=> -2a < -2c
=> -2a + 1 < -2c + 1
=> A -2a + 1 < A - 2c + 1
=> 식 1은 식 2보다 항상 작다.
항상 최대값을 갱신하기 위해 우선순위 큐를 활용한다.
*/
long long solution(int n, vector<int> works) {
priority_queue<int> pq(works.begin(), works.end());
while(n > 0){
if(pq.top() > 0){
int temp = pq.top();
pq.pop();
pq.push(temp-1);
n--;
}
else{
break;
}
}
long long answer = 0;
while(!pq.empty()){
long long temp = pq.top();
pq.pop();
answer += (temp*temp);
}
return answer;
}
3) 네트워크 (58%)
=> 풀다 말음..,
* IT 수다