[코테 - python] 백준 1744번 수 묶기

1. 문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

2. 내가 푼 답안

"""
시간복잡도를 생각해보자.
O(n) : data를 담는다.
O(n log n) : 정렬한다.

총 : O(n log n)
"""
from collections import deque

####### data에 담는다. #######
n = int(input())
data = []
for _ in range(n):
    num = int(input())
    data.append(num)

answer = 0

max_num = deque()
zero = deque()
min_num = deque()

for i in range(len(data)):
    if data[i] > 0:
        max_num.append(data[i])
    elif data[i] < 0:
        min_num.append(data[i])
    else:
        zero.append(data[i])

####### 양수 값 처리한다. #######
max_num = deque(sorted(max_num, reverse=True))
temp = len(max_num) // 2
if len(max_num) >= 2:
    for j in range(temp):
        if max_num[0] != 1 and max_num[1] != 1:
            answer += (max_num.popleft() * max_num.popleft())
        elif max_num[0] == 1:
            break

for j in range(len(max_num)):
    answer += max_num[j]

####### 음수 값 처리한다. ######
min_num = deque(sorted(min_num))
temp = len(min_num) // 2
if (len(min_num)) >= 2:
    for j in range(temp):
        answer += (min_num.popleft() * min_num.popleft())

if len(zero) > 0:
    pass
else:
    for k in range(len(min_num)):
        answer += min_num[k]

print(answer)

 

3. 문법 정리

고려해야할 것이 많은 문제였다. 먼저 양수와 음수로 숫자를 구분한다. 그리고 양수는 내림차순으로 정렬, 음수는 오름차순으로 정렬한다. 그리고 두개씩 곱하고 더해준다.

 

즉, 순서는 다음과 같다.

 

1) 양수와 음수를 따로 리스트에 담는다.

 

max_num = [1, 2, 3]
min_num = [-2, -4, -5]

 

2) 그리고 양수는 내림차순 정렬, 음수는 오름차순 정렬한다.

 

max_num = [3, 2, 1]
min_num = [-5, -4, -2]

 

3) max_num과 min_num 각각 한개가 남을 때까지 두개씩 곱해주고 더해준다.

 

4) 그 후, 남은 리스트의 값은 더해준다.

 

여기서 예외처리를 해야할 부분은 1과 0!

만약 1이 나오면 더해줘야하고, 0이 있다면 음수 부분에 남은 것을 0과 곱해서 처리한다.

 

참고로, 정렬의 시간복잡도 : O(n log n) 이라는 것을 기억하자.