[1744] 수 묶기 ( 수를 묶어서 최댓값 만들기, 우선순위 큐)

2023. 6. 1. 04:03·Coding Test/Geedy
728x90
 

1744번: 수 묶기

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에

www.acmicpc.net

 

분석

  • 양수 : 가능한 큰 수들끼리 묶음
  • 음수: 음수끼리 곱해서 양수로 더함
  • 0 : 음수가 남는경우 0을 곱함
  • 1 : 다 더함

 

풀이

import sys
input=sys.stdin.readline
from queue import PriorityQueue

pq = PriorityQueue() # 양수처리
mq = PriorityQueue() # 음수처리
one=0
zero=0

n=int(input())
for _ in range(n):
    data=int(input())
    if data>1:
        pq.put(data*-1) # 내림차순 정렬을 위해 -1을 곱해서 저장
    elif data==1:
        one+=1
    elif data==0:
        zero+=1
    else:
        mq.put(data)


sum=0

# 양수 처리
while pq.qsize() > 1:
    tmp= pq.get()*pq.get()
    sum+=tmp

if pq.qsize() > 0:
    sum+=pq.get()*-1

# 음수 처리
while mq.qsize() > 1:
        tmp = mq.get()*mq.get()
        sum += tmp

# 음수 큐에 데아터 남아있고 0이 한개도 없으면
if mq.qsize() > 0:
    if zero==0:
        sum+=mq.get()

sum+=one

print(sum)

 

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/Geedy' 카테고리의 다른 글
  • [2457] 공주님의 정원
  • [1026] 보물
  • [1715] 카드 정렬하기 (우선순위 큐)
  • [11047] 동전0 (동전개수의 최솟값 구하기)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Algorithm
    알고리즘
    스택
    DFS
    재귀
    LIS
    플로이드워셜
    DP
    정렬
    BFS
    자료구조
    그래프
    구간합
    파이썬
    힙
    구현
    큐
    덱
    이분탐색
    월간코드챌린지
    프로그래머스
    동적계획법
    최단거리
    백준
    최대공약수
    그리디
    트리
    최소신장트리
    조합
    다익스트라
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[1744] 수 묶기 ( 수를 묶어서 최댓값 만들기, 우선순위 큐)
상단으로

티스토리툴바