백준 1744 파이썬(그리디)

그리디 문제인만큼 어떤 딱 떠오르는 아이디어를 찾으려고 하기보다는 생각나는대로 생각을 이어가보았다..!!

 

우선 양수와 음수를 따로 리스트로 변수설정을 해줬다.

양수 리스트에서는 큰 수 끼리 곱해서 더해줄 떄 가장 큰 값을 가지므로 내림차순,

음수 리스트는 작은수 끼리 곱해서 더해줄 때 (음수 * 음수 = 양수)가 되므로 오름차순으로 정렬했다.

 

그리고 큐 자료구조를 이용해서 양수,음수 리스트에서 하나하나 빼가면서 나중에 한꺼번에 곱해줄 리스트(ans)에 추가해줬다(append)

 

이후 조건에 대한 자세한 설정은

문제에 나와있는 예제들을 하나하나 만족시켜가면서 만들어 본 것이다.

 

운좋게 한번에 통과가 되었다.

 

역시 그리디 문제는 겁먹지 말고 조금 지저분한데 싶더라도 일단 해보는게 가장 좋은 전략인듯 싶다! 

# 1744 수 묶기
from collections import deque

n = int(input())

li = []
for _ in range(n):
    li.append(int(input()))

positive = [num for num in li if num > 0]
negative = [num for num in li if num < 0]
positive.sort(reverse=True)
negative.sort()
pos_queue = deque(positive)
neg_queue = deque(negative)

ans = []
while pos_queue:
    if len(pos_queue) >= 2:    
        a = pos_queue.popleft()
        b = pos_queue.popleft()
        if b == 1:
            ans.append(a)
            ans.append(b)
        else:
            ans.append(a*b)
    else:
        ans.append(pos_queue.popleft())

while neg_queue:
    if len(neg_queue) >= 2:    
        a = neg_queue.popleft()
        b = neg_queue.popleft()
        ans.append(a*b)
    else:
        break

if 0 in li:
    print(sum(ans))
elif neg_queue:
    print(sum(ans)+neg_queue.popleft())
else:
    print(sum(ans))