034 수 묶기

첫번째 코드

 

역시! 그리디 알고리즘을 이용하자

그리고 033번 문제를 풀고 난 후 문제를 접한 것이여서 비슷한 느낌으로 풀면 되겠구나! 라는 생각이 금방 들었다.

가장 큰 숫자끼리 곱하는 것이 큰 수가 나오므로 priority queue를 이용해야 한다.

 

양수인 경우, 음수인 경우 나누어 진행한다.

(priority queue는 오름차순으로 정리되기 때문에 양수에 -1을 곱하여 가장 큰 수가 가장 앞에 오도록 해야한다!!!)

음수가 남으면 0을 더하게 되면 좋으므로 일단 빼두고 나중에 음수가 남는 경우에 더한다.

1은 곱하는 것에 의미가 없기 때문에 무조건 더한다!

 

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

n = int(input())
plus_queue = PriorityQueue()
minus_queue = PriorityQueue()
one = 0
zero = 0
a = 0
b= 0
sum = 0

for i in range(n):
    data = int(input())
    if data > 1:
        plus_queue.put(data * (-1))
    elif data == 1:
        one += 1
    elif data == 0:
        zero += 1
    else:
        minus_queue.put(data)
        

while plus_queue.qsize() > 1:
    a = plus_queue.get() * (-1)
    b = plus_queue.get() * (-1)
    sum += a * b

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

while minus_queue.qsize() > 1:
    a = minus_queue.get()
    b = minus_queue.get()
    sum += a * b

if minus_queue.qsize() > 0:
    if zero == 0:
        sum += minus_queue.get()

sum += one
print(sum)

 

통과!

그래도 다시 풀면 풀 수 있겠다는 확신!

DFS와 BFS에서는 그런 느낌이 안들어서 풀이 죽어있었는데 ㅎㅎ;;

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1744.%E2%80%85%EC%88%98%E2%80%85%EB%AC%B6%EA%B8%B0

programmers/백준/Gold/1744. 수 묶기 at main · ornni/programmers