[백준] 1744번 : 수 묶기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1744번: 수 묶기

 

1. 문제 설명

2. 풀이과정

문제에서 N의 최대 범위가 10,000이므로 시간 복잡도와 관련된 제약은 적다.
문제의 핵심을 생각해 보면 가능한 큰 수들끼리 묶어야 최종 결괏값이 커진다는 것을 알 수 있다.
또한 음수가 들어올 수 있으므로 음수와 음수를 곱하면 양수가 되는 것도 잘 고려해야 한다.
 
입력으로 들어오는 수를 총 4가지로 구분해 보면 [음수, 0, 1, 양수]로 구분할 수 있다.
1을 따로 구분한 이유는 1을 포함하여 수를 묶는 것보다 1을 따로 더하는 것이 결과가 더 커지기 때문이다.
또한 0을 포함하여 수를 묶으면 해당 결과는 0이 되므로 0도 따로 구분해 준다.
4가지 유형으로 값을 구분해 저장해 주고 양수와 음수의 절댓값이 큰 값부터 묶어주면 최종 결과가 커진다.
양수의 개수가 홀수이면 남은 수는 그대로 더해준다.
하지만 음수의 개수가 홀수이면 0의 개수를 파악하고 0이 있다면 0과 묶어 음수를 제거한다.
 
슈도코드

1. N(수열의 크기) 입력받기
2. plusQ(양수 저장할 우선순위 큐)
3. minusQ(음수 저장할 우선순위 큐)
4. one(1의 개수 저장)
5. zero(0의 개수 저장)
6. for N만큼 반복: 데이터를 입력받아 4가지 유형에 분리하여 저장
7. (이때, 양수 우선순위 큐는 내림차순 정렬을 위해 -1을 곱하여 저장함)
8. while (양수 우선순위 큐 크기가 2보다 작을 때까지):
   1. 수 2개를 큐에서 뽑음
   2. 2개의 수를 곱한 값을 결과에 더함
9. if (양수 우선순위 큐의 데이터가 남아 있으면 = 홀수개): 해당 데이터를 결과에 더함
10. (내림차순 정렬을 위해 -1을 곱하여 저장했으므로 -1을 다시 곱하여 더해줌)
11. while (음수 우선순위 큐 크기가 2보다 작을 때까지 반복):
    1. 수 2개를 큐에서 뽑음
    2. 2개의 수를 곱한 값을 결과에 더함
12. if (음수 우선순위 큐의 데이터가 남아 있으면 = 홀수개):
    1. if (0이 아예 없으면): 남은 데이터를 결과에 더함
13. 숫자 1의 개수를 결과에 더함
14. 결과 출력

반응형

3. 소스코드

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())

plusQ = PriorityQueue()
minusQ = PriorityQueue()
one = 0
zero = 0
for _ in range(N):
    num = int(sys.stdin.readline())
    if (num > 1):
        plusQ.put(num * -1)
    elif (num == 1):
        one += 1
    elif (num == 0):
        zero += 1
    else:
        minusQ.put(num)

result = 0

while (plusQ.qsize() > 1):
    num1 = plusQ.get()
    num2 = plusQ.get()
    result += num1 * num2

if (plusQ.qsize() > 0):
    result += plusQ.get() * -1

while (minusQ.qsize() > 1):
    num1 = minusQ.get()
    num2 = minusQ.get()
    result += num1 * num2

if (minusQ.qsize() > 0):
    if (zero == 0):
        result += minusQ.get()

result += one
print(result)