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)