[#1744] 수 묶기

문제

#1744 수 묶기
Gold4
적용 알고리즘: 정렬 알고리즘

---

풀이 방법

• 음수 배열, 양수 배열로 나누어 따로 계산
• 양수 배열: 내림차순으로 정렬 후, 큰 수 두개끼리 곱하고 합한 값 중 더 큰 값을 총합에 더함. 홀수일 경우 마지막 수를 단독으로 총합에 더함
• 음수 배열: 오름차순으로 정렬 후, 작은 수 두개끼리 곱함.
• 두개의 수가 다 음수이기 때문에 합한 값은 무조건 음수이므로 곱한 값이 클 수밖에 없음
• 0은 존재 여부만 획인하면 됨 -> 만일 음수가 홀수일 경우 가장 큰 음수(음수 중 절댓값이 작은 수)에 0을 곱함. 0이 없다면 절댓값이 가장 작은 음수를 총합에 더함

코드 흐름

1. 사용자가 입력하는 수들을 각각 음수 배열, 양수 배열에 추가하고, 만일 0이 있다면 0의 존재를 True로 설정한다.
2. 양수 배열은 내림차순으로, 음수배열은 오름차순으로 정렬한다.
3. 양수 배열 계산
   1. 첫 번째 항목과 두번째 항목의 합의 값과 곱의 값을 구한다.
   2. 두 수중 더 큰 수를 총합(sum)에 더한다.
   3. 인덱스를 2만큼 증가시킨다.
   4. 만일 양수배열의 길이가 홀수라면, 마지막 원소를 총합에 따로 더해준다.
4. 음수 배열 계산
   1. 첫 번째 항목과 두번째 항목의 곱을 총합에 더한다.
   2. 만일 음수 배열의 길이가 홀수이고 0이 입력에서 존재하지 않는다면, 음수 배열의 마지막 원소를 총합에 더해준다.(입력에 0이 존재하는 경우 음수 배열의 마지막 원소는 0과 곱해져서 상쇄되므로 더해주지 않아도 된다.)
5. 총합을 출력한다.

코드

n = int(input())

plus = []
minus = []
zero = False
for _ in range(n):
    temp = int(input())
    if (temp > 0):
        plus.append(temp)
    elif (temp < 0):
        minus.append(temp)
    else:
        zero = True

plus.sort(reverse=True)
minus.sort()

sum = 0

# 양수 배열 계산
idx = 0
while (idx < len(plus) - 1):
    temp_mul = plus[idx] * plus[idx + 1]
    temp_add = plus[idx] + plus[idx + 1]
    if (temp_mul > temp_add):
        sum += temp_mul
    else:
        sum += temp_add
    idx += 2
if (len(plus) % 2 != 0):
    sum += plus[-1]

# 음수 배열 계산
idx = 0
while (idx < len(minus) - 1):
    sum += minus[idx] * minus[idx + 1]
    idx += 2
if (len(minus) % 2 != 0 and zero == False):
    sum += minus[-1]

print(sum)

체감 난이도: 3.5/5
어려운 문제는 아니고 발상을 어떻게 하느냐가 관건이었던 문제인 것 같다. 처음에는 입력된 배열을 하나의 배열로 저장하여 통째로 정렬하여 풀었는데, 이렇게 되는 경우 양수에서 음수로 넘어가는 부분의 계산이 복잡해지게 되어 배열을 양수, 음수로 분리하였다. 또한 0은 입력 개수와 상관없이 존재 하느냐/하지 않느냐의 여부만 확인해도 된다는 것을 아는 것이 또 하나의 키 포인트인것 같다.
이 문제를 풂으로써 드디어 백준 티어가 실버로 올라갔다ㅋㅋ 옛날에 문제는 많이 풀고 백준에 채점은 하지 않았었는데 진작에 채점도 할 걸 그랬다…