[백준 - Python] 1744. 수 묶기 (그리디)

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

코드

n = int(input())

plus = []
minus = []

total = 0
for i in range(n):
    num = int(input())
    if num > 1:
        plus.append(num)
    elif num <= 0:
        minus.append(num)
    else:
        total += 1

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

for i in range(0, len(plus), 2):
    if i+1 >= len(plus):
        total += plus[i]
    else:
        total += (plus[i] * plus[i+1])

for i in range(0, len(minus), 2):
    if i+1 >= len(minus):
        total += minus[i]
    else:
        total += (minus[i] * minus[i+1])

print(total)

 

문제를 읽고 떠올린 아이디어는

1. 0이 있다면, 수열의 가장 큰 음수랑 곱하기

2. 양수들은 내림차순 정렬 후, 숫자 2개씩 순차적으로 곱하기

3. 음수들은 오름차순 정렬 후, 숫자 2개씩 순차적으로 곱하기

4. 1은 곱하지 말고 그냥 더하기

였다.

 

하나의 리스트에 숫자 전체를 입력 받고 0을 처리하고, 1을 처리하고

그 후에 양수와 음수가 바뀌는 지점을 파악해 2, 3번 연산을 수해하는 방식으로 구현을 했다.

 

일단 내가 생각한 아이디어의 문제점은 1번이다.

나는 절댓값이 가장 큰 음수를 0이 있으면 제거를 하는게 최댓값일 거라 생각했는데,

음수가 여러 개일 경우에는 큰 음수들끼리 곱하는 것이 전체 합을 키우는 방법임으로

음수가 홀수 개인 경우에 남는, 절댓값이 가장 작은 음수와 0을 곱해주는 것이 해답 아이디어였다.

 

또한 전체 숫자를 하나의 리스트에 입력 받은 것도 비효율적인 풀이였던 것 같다.

애초에 입력을 받으면서 숫자가 양수인지 음수인지 판별 후,

각각 다른 리스트로 관리하면 더 수월하게 문제를 해결할 수 있었지 않았을까 싶다.

 

항상 숫자의 나열이 들어오면,

num = list(map(int, input().split())) 을 습관처럼 쓰다보니까

더 간결하게 풀 수 있는 간단한 생각을 하지 못한 것 같다.

 

나는 양수와 음수 리스트에서 숫자를 두 개씩 곱해주는 연산을 할 때,

while True 문과 특정 탈출 변수를 활용한 풀이를 시도했었다.

 

처음에는 참고한 코드처럼 for문을 활용해서 풀 생각을 했었지만,

인덱스를 적절하게 활용해 리스트 요소가 홀수 개일 때,

마지막 남은 요소는 더해주는 코드를 짜는데 어려움을 겪었다.

 

해당 부분을 복습하면 좋을 것 같다.

 

코드 참고

https://subinze.tistory.com/320