😢 백준 1339 : 단어 수학

1744: 수 묶기

Greedy 문제이다.
아이디어는 바로 생각나는 문제였다. 근데 좀 헤맸다. 😥😥

📌 Try 1

from collections import deque

# 빈 큐 만들기
N = int(input())
inputArr = list()
for _ in range(N):
  inputArr.append(int(input()))
  
inputArr.sort()
nums, _sum = deque(inputArr), 0

# plus
while len(nums) >= 2 and nums[-1] > 0:
  n2, n1 = nums.pop(), nums.pop()
  if n2 <= 0:
      nums.append(n1)
      nums.append(n2)
      break
  elif n1 <= 0:
      nums.append(n1)
      _sum += n2
      break
  _sum += n1 * n2
  
  # print(_sum, nums)
  
if nums and nums[-1] > 0:
  _sum += nums.pop()
# print('middle', _sum, nums)

# minus
while len(nums) >= 2:
  n1, n2 = nums.popleft(), nums.popleft()
  _sum += n1 * n2
  # print(_sum, nums)

if nums:
  _sum += nums.pop()

print(_sum)

코드가 아주아주 더럽다..
머리 아파서 대충 풀고 넘기려고 했지만, 여러 차례 틀렸다.

📌 Try 2

from collections import deque

N = int(input())
minusArr, plusArr, _sum = list(), list(), 0
for _ in range(N):
    n = int(input())
    if n > 0:
        plusArr.append(n)
    else:
        minusArr.append(n)
        
plusArr.sort()
minusArr.sort(reverse=True)

while len(plusArr) >= 2:
  n1, n2 = plusArr.pop(), plusArr.pop()
  _sum += n1 * n2

if plusArr:
  _sum += plusArr.pop()
  
while len(minusArr) >= 2:
  n1, n2 = minusArr.pop(), minusArr.pop()
  _sum += n1 * n2

if minusArr:
  _sum += minusArr.pop()

print(_sum)

이번엔 양수, 0, 음수를 담는 list를 따로 담아서 풀었다.

깔끔하게 풀었고, 당연히 정답일 줄 알았는데 시간초과 떴다.

📌 Try 3

from collections import deque

N = int(input())
minusArr, plusArr, _sum = list(), list(), 0
for _ in range(N):
    n = int(input())
    if n > 1:
        plusArr.append(n)
    elif n == 1:
        _sum += 1
    else:
        minusArr.append(n)
        
plusArr.sort()
minusArr.sort(reverse=True)

while len(plusArr) >= 2:
  n1, n2 = plusArr.pop(), plusArr.pop()
  _sum += n1 * n2

if plusArr:
  _sum += plusArr.pop()
  
while len(minusArr) >= 2:
  n1, n2 = minusArr.pop(), minusArr.pop()
  _sum += n1 * n2

if minusArr:
  _sum += minusArr.pop()

print(_sum)

도저히 방법을 몰라서 다른 분 블로그를 참고했다.

문제점 :

1은 다른 연산 없이 바로 더해야 가장 합이 커진다는 것이다.

📌 Try 2 코드에서 해당 부분만 수정해주니까 맞았습니다!!가 떴다.

🎁 Reference

• 파이썬 백준 1744번 수 묶기
  https://velog.io/@sch804/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1744%EB%B2%88-%EC%88%98-%EB%AC%B6%EA%B8%B0