[백준] [정렬] 1744. 수 묶기

1744. 수 묶기

1744번: 수 묶기

 

 

• 내 풀이
  • sort사용하면 시간초과 날것 같아서 퀵소트 구현
    • => 퀵소트랑 .sort()랑 시간이 같다 ㅇ0ㅇ!!!!!!!!
  • 곱한 값 > 더한 값이어서 그룹지으면 index-2
  • 더한값이 더 크면 그룹 안짓고 index-1
  • 음수끼리 곱하면 양수이므로 가장 작은값끼리 곱하면 가장 큰값이 됨
    • 음수 개수가 홀수 개일때 
      
      • 0 이 있으면:
        • 음수 중 가장 큰 값 소멸시키기
        • 어짜피 음수 중 한가지값만 소멸하면 되므로 0있는지만 체크
      • 0이 없으면: 음수 중 가장 큰값 result에 더해주기
      • 나머지 값들은 곱해서 result에 더해주기
    • 음수 개수가 홀수개면 곱하거나 각각 더한 것중 더 큰 값으로 

def quick(lst,start,end):
    if start>=end: #lst길이가 1이면 종료
        return

    pivot=start
    left=start+1 #pivot 다음 값부터 확인
    right=end

    while left<=right:
        while left<=end and lst[left]<=lst[pivot]:
            left+=1
        while right>start and lst[right]>=lst[pivot]:
            right-=1

        if left<=right: #엇갈리지 않은경우
            lst[left], lst[right]= lst[right], lst[left]
        else:
            lst[right], lst[pivot]= lst[pivot], lst[right]

    quick(lst, start, right-1)
    quick(lst, right+1, end)

n=int(input())
lst=[]
result=0

for _ in range(n):
    lst.append(int(input()))

quick(lst, 0, n-1)

idx=n-1
cnt=1 #0 없으면 음수 곱해서 더할 수 있게 1
flag=0 #첫 음수확인
while idx>=0:
    if lst[idx]==0:
        idx-=1
        cnt=0 #0이 있으면 0 -> 곱해서 음수 없앨 수 있게
        continue

    if lst[idx]<0 and flag==0: #처음으로 음수 나왔을 경우(음수 중 가장 큰값)
        flag=1
        if len(lst[:idx+1])%2!=0 : #음수 개수가 홀수면
            result+=lst[idx]*cnt #0이 있으면 없애고 있으면 더함
            idx -= 1
        continue

    if lst[idx]*lst[idx-1]>lst[idx]+lst[idx-1] and idx>=1:
        result+=lst[idx]*lst[idx-1]
        idx-=2
    else:
        result+=lst[idx]
        idx-=1

print(result)

 

• 다른 사람 풀이
  • 값이 1이상이면 무조건 곱하는게 더하는 것보다 값이 크다
    • 더하는 경우는 값 중 하나가 1일때만!!!
    • → 1이상이면 그룹짓고 (pop)
    • 리스트에 남은 값들은 1만 남으므로 마지막에 전부 더해준다 
  • 작은 값부터 두 수 뽑는데 음수,0 이 나오면 
  • → 음수개수가 홀수개라는 뜻이므로 그냥 똑같이 곱해서 없애주기

from collections import deque

N = int(input())
arr = []
result = 0

for _ in range(N):
    arr.append(int(input()))
arr.sort(reverse=True)
q = deque(arr)

while len(q)>1:
    if q[0]>1 and q[1]>1:
        num1 = q.popleft()
        num2 = q.popleft()
        result+=num1*num2
    else:
        break

while len(q)>1:
    if q[-1]<=0 and q[-2]<=0:
        num1 = q.pop()
        num2 = q.pop()
        result += num1*num2
    else:
        break

print(result+sum(list(q)))