알고리즘 (PS)/Programmers

[프로그래머스] 이중우선순위큐

2025. 3. 22. 00:19
반응형

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

백준에도 똑같은 문제가 있다.

전에 프로그래머스 레벨 테스트에서 이 문제를 만났다가 구현에서 막혀서 못 풀었던 기억이 났다.

(백준에서도 힘들게 풀었었는데..)

 

이번에 다시 풀어볼 때는 한번에 잘 풀려서 기분이 좋았다. (옛날 풀이는 기억이 나지 않고 완전히 새로운 느낌으로 풀었다.)

이 문제의 핵심은 최소힙과 최대힙을 만들고, 이 둘 사이에 데이터 동기화를 잘 시켜주는 것이다.

 

먼저 데이터를 추가할 때는 두 힙에 모두 데이터를 추가한다.

최솟값을 삭제할 때는 최소힙에서 데이터를 삭제하고, 최댓값을 삭제할 때는 최대힙에서 데이터를 삭제한다.

 

데이터를 삭제할 때마다 deleted 딕셔너리에 삭제한 수를 키로 넣고, 삭제한 횟수를 value 로 저장한다.

그리고, 최솟값을 삭제하기 전에 현재 pop 한 숫자가 다른 힙에서 삭제된 수인지 deleted 딕셔너리를 확인해서 이미 삭제된 수는 빼고 나서 삭제한다.

최댓값도 삭제하기 전에 deleted 배열을 보고 이미 삭제된 수인지 확인해서 동기화 시켜준 뒤 삭제한다.

 

최종적으로 최댓값, 최솟값을 뺄 때도 같은 방식으로 최댓값, 최솟값을 한번씩 뺀다.

이때 이중우선순위큐에 최종 데이터가 1개 남아있을 수도 있는 점만 주의해주면 된다.

 

from heapq import heappush, heappop

def solution(operations):
    max_heap = []
    min_heap = []
    deleted = dict()
    
    for op in operations:
        op, data = op.split()
        data = int(data)
        if op == 'D':
            if data == 1: # delete max
                while max_heap and max_heap[0][1] in deleted and deleted[max_heap[0][1]] > 0:
                    _, popped = heappop(max_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
                    deleted[popped] -= 1
                if max_heap:
                    _, popped = heappop(max_heap)
                    if popped in deleted:
                        deleted[popped] += 1
                    else:
                        deleted[popped] = 1
            else:
                while min_heap and min_heap[0][1] in deleted and deleted[min_heap[0][1]] > 0:
                    _, popped = heappop(min_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
                    deleted[popped] -= 1
                if min_heap:
                    _, popped = heappop(min_heap)
                    if popped in deleted:
                        deleted[popped] += 1
                    else:
                        deleted[popped] = 1
        else:
            heappush(max_heap, (-data, data))
            heappush(min_heap, (data, data))
    
    # pop max
    popped_max = None
    popped_min = None
    while max_heap and max_heap[0][1] in deleted and deleted[max_heap[0][1]] > 0:
        _, popped = heappop(max_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
        deleted[popped] -= 1
    if max_heap:
        _, popped = heappop(max_heap)
        popped_max = popped
        if popped in deleted:
            deleted[popped] += 1
        else:
            deleted[popped] = 1
            
    # pop min
    while min_heap and min_heap[0][1] in deleted and deleted[min_heap[0][1]] > 0:
        _, popped = heappop(min_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
        deleted[popped] -= 1
    if min_heap:
        _, popped = heappop(min_heap)
        popped_min = popped
        if popped in deleted:
            deleted[popped] += 1
        else:
            deleted[popped] = 1
    
    if popped_max == None and popped_min == None:
        return [0, 0]
    
    if popped_max == None:
        popped_max = popped_min
    
    if popped_min == None:
        popped_min = popped_max
    
    return [popped_max, popped_min]

 

중복되는 코드가 많아서 조금 더 깔끔하게 정리하면

 

from heapq import heappush, heappop

def solution(operations):
    max_heap = []
    min_heap = []
    deleted = dict()
    
    def delete_max():
        while max_heap and max_heap[0][1] in deleted and deleted[max_heap[0][1]] > 0:
            _, popped = heappop(max_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
            deleted[popped] -= 1
        if max_heap:
            _, popped = heappop(max_heap)
            if popped in deleted:
                deleted[popped] += 1
            else:
                deleted[popped] = 1
            
            return popped
        return None
    
    def delete_min():
        while min_heap and min_heap[0][1] in deleted and deleted[min_heap[0][1]] > 0:
            _, popped = heappop(min_heap) # 과거에 삭제된 기록이 있는 데이터 삭제
            deleted[popped] -= 1
        if min_heap:
            _, popped = heappop(min_heap)
            if popped in deleted:
                deleted[popped] += 1
            else:
                deleted[popped] = 1
            return popped
        
        return None
    
    for op in operations:
        op, data = op.split()
        data = int(data)
        if op == 'D':
            if data == 1: # delete max
                delete_max()
            else:
                delete_min()
        else:
            heappush(max_heap, (-data, data))
            heappush(min_heap, (data, data))
    
    popped_max = delete_max()
    popped_min = delete_min()
    
    if popped_max == None and popped_min == None:
        return [0, 0]
    
    if popped_max == None:
        popped_max = popped_min
    
    if popped_min == None:
        popped_min = popped_max
    
    return [popped_max, popped_min]

 

그런데 delete 함수에서도 중복되는 코드가 보인다.

더 중복코드를 깔끔하게 분리해보자.

 

from heapq import heappush, heappop

def solution(operations):
    max_heap = []
    min_heap = []
    deleted = dict()
    
    def delete(heap):
        while heap and heap[0][1] in deleted and deleted[heap[0][1]] > 0:
            _, popped = heappop(heap) # 과거에 삭제된 기록이 있는 데이터 삭제
            deleted[popped] -= 1
        if heap:
            _, popped = heappop(heap)
            if popped in deleted:
                deleted[popped] += 1
            else:
                deleted[popped] = 1
            
            return popped
        return None
    
    for op in operations:
        op, data = op.split()
        data = int(data)
        if op == 'D':
            if data == 1: # delete max
                delete(max_heap)
            else:
                delete(min_heap)
        else:
            heappush(max_heap, (-data, data))
            heappush(min_heap, (data, data))
    
    popped_max = delete(max_heap)
    popped_min = delete(min_heap)
    
    if popped_max == None and popped_min == None:
        return [0, 0]
    
    if popped_max == None:
        popped_max = popped_min
    
    if popped_min == None:
        popped_min = popped_max
    
    return [popped_max, popped_min]

 

최종코드는 위와 같다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 (PS) > Programmers' 카테고리의 다른 글

[프로그래머스] 시험장 나누기 (2021 카카오 채용연계형 인턴십)  (0) 2025.03.21
[프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT)  (0) 2025.03.20
[프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)  (0) 2024.11.22
[프로그래머스/python3] 다트 게임 (2018 KAKAO BLIND RECRUITMENT [1차])  (0) 2022.11.13
'알고리즘 (PS)/Programmers' 카테고리의 다른 글
  • [프로그래머스] 시험장 나누기 (2021 카카오 채용연계형 인턴십)
  • [프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT)
  • [프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)
  • [프로그래머스/python3] 다트 게임 (2018 KAKAO BLIND RECRUITMENT [1차])
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (591) N
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (315) N
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (15) N
      • 기계학습심화 (12)
    • 자기계발 (36) N
      • 동아리 (7)
      • 자격증 (2)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (18) N
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[프로그래머스] 이중우선순위큐
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.