LEVEL 3 : 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

• 문제

  • 

    문제

 

---

풀이

• 우선 순위 큐 2개를 선언해서 풀어주었다
• 우선 순위 큐
  • 1번 큐. 작은 것부터 높은 우선순위를 가지는 큐 
  • 2번 큐. 큰 값부터 높은 우선순위를 가지는 큐 
• I : 숫자를 우선순위 큐 모두에 넣어준다
• D 1 큐 1,2 에서 값 모두 제거한다
  • 2번 큐의 값을 빼준뒤, 1번 큐의 remove함수를 호출해 값을 삭제해준다.
• D -1 큐 1,2 에서 값 모두 제거한다
  • 1번 큐의 값을 빼준뒤, 2번 큐의 remove함수를 호출해 값을 삭제해준다.
• 두개의 큐 모두 비어있지 않다면 최댓값 최솟값을 반환한다. 

• public int[] solution(String[] operations) {
  	int[] answer = new int[2];
      Queue<Integer> max = new PriorityQueue<>((o1,o2)->o2-o1); //높은 값 높은 우선순위
      Queue<Integer> min = new PriorityQueue<>((o1,o2)->o1-o2); //낮은 값 높은 우선순위
      for(String oper : operations) {
      	StringTokenizer tokens = new StringTokenizer(oper);
          String op = tokens.nextToken();
          int number = Integer.parseInt(tokens.nextToken());
      		if(op.equals("I")) {//연산자 I
      			min.offer(number); //두개의 큐 모두에 값을 넣어준다
      			max.offer(number);
              }else if(op.equals("D")) { //삭제일 경우
      			if(max.isEmpty() || min.isEmpty()) // 큐에 데이터가 없다면 둘다 지우면 안된다
      				continue;
      			if(number > 0) { //max값을 뺸뒤 제일 큰값만 빼준다.
      				int m = max.poll();
      				min.remove(m);
      			}else {
      				int m = min.poll();//min값을 뺀뒤 제일 작은값만 빼준다
      				max.remove(m);
      			}
      		}
      	}
      	if(!min.isEmpty() && !max.isEmpty()) {//모두 비어있지 암ㅎ다면
      		answer[0] = max.poll();
      		answer[1] = min.poll();//최대최소 반환
      	}
      	return answer;
      }