BOJ/그리디

1744. 수 묶기 - 그리디. 정렬. 파이썬.

쓱쓱565 2021. 10. 9. 10:03

1744. 수 묶기


사용한 알고리즘/자료구조
1. 그리디
2. 정렬

접근 방식
입력받은 숫자들을 아래의 4종으로 구분해 정리한다. 
1) 0
2) 1
3) 1이 아닌 양의 정수
4) 음의 정수

각각의 활용법은 다음과 같다.

1) 0 

음의 정수에 곱해줘서 0으로 만든다. 단 음수가 2개 이상일 경우 음수끼리 서로 짝지어서 합에 더하는게 이득이다. 음수의 갯수가 홀수일 때, 가장 절댓값이 작은 1개의 음수에만 0을 곱해 소거하면 된다. 따라서 0은 True/False 로 존재 여부만 확인한다. 


2) 1 

갯수만큼 total 에 더한다.

 

3) 1이 아닌 양의 정수
큰 것 부터 2개씩 짝지어서 곱한 후 total 에 더한다.

 

4) 음의 정수
절댓값이 큰 것부터 2개씩 짝지어서 곱한 후 total 에 더한다.

문제 특이사항
입력 전처리를 잘 하면 연산량을 많이 줄일 수 있다.

어려웠던 점
1의 예외처리

문제를 풀었을 당시의 백준 티어
골드2, 2021-10-09

 

from sys import stdin

# 1. 입력
N = int(stdin.readline()) # 숫자들의 갯수

# 1-1. 입력 전 준비
negative = []  # 음수들을 저장할 리스트
positive = []  # 양수들을 저장할 리스트
zeros = False  # 0이 있는지 확인할 스위치
ones = 0  # 1의 갯수를 세는 변수

# 1-2. 입력
for i in range(N):
    number = int(stdin.readline())  # 숫자를 입력받는다

    # 1) 0 일때
    if not number:
        zeros = True  # 수열에 0 이 있다고 표시

    # 2) 1일때
    elif number == 1:
        ones += 1  # 의 갯수 가산.

    # 3) 양의 정수일 때
    elif number > 0:
        positive.append(number)  # 양의 정수 목록에 추가.

    # 4) 음의 정수일 때
    else:
        negative.append(number)  # 음의 정수 목록에 추가

# 1-3 입력값 정렬
negative.sort(reverse=True) # 정렬. pop() 연산을 사용하기 위해 내림차순 정렬.
positive.sort() # 정렬.


# 2. 선언
total = 0  # 결과를 입력받을 변수 선언


# 3. 연산
# 1) 양수 연산
while len(positive) > 1:  # 양수끼리 짝을 지을 수 있을 때까지
    total += positive.pop() * positive.pop()  # 가장 큰 양수들끼리 곱한 후 합에 더한다.

if positive:  # 짝을 안 지은 양수가 남았다면
    total += positive[0]  # 양수를 합에 더한다.

# 2) 음수 연산
while len(negative) > 1:  # 음수끼리 짝을 지을 수 있을 때까지
    total += negative.pop() * negative.pop()  # 절대값이 가장 큰 음수들끼리 더한 후 합에 더한다.

if not zeros and negative:  # 음수가 하나 남았고 0과 곱해줄 수도 없다면
    total += negative[0]   # 음수를 합에 더해준다.

# 3) 1 연산
total += ones  # 1의 갯수들을 합에 더해준다.

# 4. 출력
print(total)