프로그래머스 3단계 : 이중우선순위큐 (Java 자바)

2023. 8. 28. 12:44·💻 코딩테스트/programmers
728x90

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

 

제한사항

  • operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
  • operations의 원소는 큐가 수행할 연산을 나타냅니다.
    • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
  • 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

 

풀이

처음엔 ArrayList를 사용하려고 했으니 최댓값, 최솟값을 구할 때 ArrayList를 사용하면 시간초과 및 효율성이 떨어진다는 걸 알게되었습니다.

이런 문제는 우선순위큐로 접근하는 게 더 좋습니다! (PriorityQueue를 사용하는 문제)

1. 최대값을 삭제할 때는 최대힙에서 poll() 을 사용하고, 최소힙에서 remove() 함수로 삭제
2. 최소값을 삭제할 때는 최소힙에서 poll() 을 사용하고, 최대힙에서 remove() 함수로 삭제

* PriorityQueue에 대한 내용은 추후 정리 후 업로드

 

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {

        int[] answer = new int[2];

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 연산
        for (String op : operations) {

            // 삽입
            if (op.substring(0,1).equals("I")) {
                int value = Integer.valueOf(op.substring(2));     
                minHeap.offer(value);
                maxHeap.offer(value);          
            } 
                     
            // 값이 있을 때
            else if (!minHeap.isEmpty()) {
                
                // 최대값 remove
                if (op.equals("D 1")) {
                    int value = maxHeap.poll();
                    minHeap.remove(value);
                }

                // 최소값 remove
                else if (op.equals("D -1")) {
                    int value = minHeap.poll();
                    maxHeap.remove(value);       
                }
            }            
        }

        // 값이 있을 때
        if (!minHeap.isEmpty()) {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }

        return answer;
    }
}
728x90

'💻 코딩테스트 > programmers' 카테고리의 다른 글

프로그래머스 2단계 : JadenCase 문자열 만들기 (Java 자바)  (0) 2023.08.28
프로그래머스 3단계 : 최고의 집합 (Java 자바)  (1) 2023.08.28
프로그래머스 2단계 : 귤 고르기 (Java 자바)  (0) 2023.08.28
프로그래머스 3단계 : 네트워크 (Java 자바)  (0) 2023.08.26
프로그래머스 3단계 : 정수 삼각형 (Java 자바)  (0) 2023.08.26
'💻 코딩테스트/programmers' 카테고리의 다른 글
  • 프로그래머스 2단계 : JadenCase 문자열 만들기 (Java 자바)
  • 프로그래머스 3단계 : 최고의 집합 (Java 자바)
  • 프로그래머스 2단계 : 귤 고르기 (Java 자바)
  • 프로그래머스 3단계 : 네트워크 (Java 자바)
gxxg
gxxg
함께 일하고 싶은 개발자를 꿈꾸는 예비개발자의 공부 기록
  • gxxg
    공공
    gxxg
  • 전체
    오늘
    어제
    • 분류 전체보기 (138)
      • ☁️ 구름 x 카카오 Deep Dive 풀스택 (7)
        • html, css (1)
        • Java (3)
        • 스프링 MVC (0)
      • 💻 코딩테스트 (89)
        • 백준 (2)
        • programmers (87)
      • SQLD (1)
      • Language (3)
        • Java (2)
        • JavaScript (1)
      • Style Sheet (0)
        • CSS (0)
        • SCSS & SASS (0)
      • DBMS (2)
        • Oracle (2)
        • MySQL (0)
        • postgresql (0)
        • 데이터베이스 기초 이론 (0)
      • React (0)
      • SpringBoot (0)
      • JSP (2)
      • 알고리즘 (0)
      • 2023-02 몰입형 SW 정규 교육 (24)
        • 9월 프로젝트 (8)
      • 벽돌깨기 (4)
      • Etc (4)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    티스토리챌린지
    Lv0
    코테
    HTML
    자바스크립트
    톰캣
    spring
    오블완
    eclipse
    3단계
    junit 테스트
    자바
    이클립스
    CSS
    구현체
    springboot
    코딩테스트
    programmers
    POST
    DFS
    Lv2
    JSP
    2단계
    프로그래머스
    회원 관리 시스템
    javascript
    LV3
    프로젝트 구조
    java
    0단계
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
gxxg
프로그래머스 3단계 : 이중우선순위큐 (Java 자바)
상단으로

티스토리툴바