[백준/BOJ][Python] 1744번 수 묶기

[백준/BOJ][Python] 1744번 수 묶기

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

1744번: 수 묶기

 

---

아이디어

양수는 내림차순, 음수는 오름차순으로 정렬하고

1이면 그냥 더하기, 음수가 짝수개이면 음수끼리 곱해서 더하기, 음수가 홀수개인데 0이 있으면 0 곱해서 더하기

그리고 리스트에서 이미 더한거는 1002로 처리

이런식으로 경우의 수를 모두 생각해서 풀었다!(정답코드1)

 

근데 더 쉬운 풀이가 있어서 다른 방법으로도 풀어봤다!!(정답코드2)

 

---

코드

 

정답 1

# 정답 코드 1
import sys
input = sys.stdin.readline

n = int(input())
arr = []
positive = []
negative = []
zero = False

arr = positive + negative
for _ in range(n):
    a = int(input())
    if a == 0: zero = True
    if a >= 0:
        positive.append(a)
    else:
        negative.append(a)
positive.sort(reverse=True)
negative.sort()
arr = positive + negative



result = 0
for i in range(n-1):
    if arr[i] > 0 and arr[i] < 1002: # 양수
        if arr[i+1] > 1 :
            result += (arr[i]*arr[i+1])
            arr[i], arr[i+1] = 1002, 1002
        else:
            result += arr[i]
            arr[i] = 1002

    elif arr[i] <= 0 and zero == False : # 음수
        if arr[i+1] < 0:
            result += (arr[i] * arr[i + 1])
            arr[i], arr[i + 1] = 1002, 1002

        else:
            result += arr[i]
            arr[i] = 0

    elif zero and arr[i] < 0:
        if arr[i+1] < 0:
            result += (arr[i] * arr[i + 1])
            arr[i], arr[i + 1] = 1002, 1002


if arr[-1] != 1002 and zero==False:
    print(result+arr[-1])
else:
    print(result)

 

 

정답2)

# 정답 코드 1
import sys
input = sys.stdin.readline

n = int(input())
positive_arr = []
negative_arr = [] # 0은 여기에 넣을 예정
result = 0

for _ in range(n):
    a = int(input())
    if a <= 0:
        negative_arr.append(a)
    elif a == 1: # 1이면 그냥 더하기
        result += 1
    else:
        positive_arr.append(a)

negative_arr.sort() # 음수는 오름차순
positive_arr.sort(reverse=True) # 양수는 내림차순

if len(positive_arr) %2 != 0:
    positive_arr.append(1)
if len(negative_arr)%2 != 0:
    negative_arr.append(1)

for i in range(0, len(positive_arr), 2):
    result += (positive_arr[i]*positive_arr[i+1])
for i in range(0, len(negative_arr), 2):
    result += (negative_arr[i]*negative_arr[i+1])
print(result)

이 코드가 조금 더 간결해보인다.

 

1은 어차피 곱해줘도 똑같으니 바로 더하고 리스트에 넣진 않는다.

코드1처럼 음수는 오름차순, 양수는 내림차순으로 정렬한다. 이때 0은 음수 리스트에 넣었다.

그 이유는 음수가 홀수개면 0을 곱해서 없애버리기 위해서이다

양수나 음수리스트가 홀수개이면 각 리스트 맨 뒤에 1을 넣는다.(어차피 1은 곱하나마나 똑같으니)

그리고 값 두 개를 곱해가면서 result에 더해준다!

그럼 끝!

 

 

 

두 코드를 비교해보면 메모리, 시간측면에서는 똑같다 걍 코드 길이 차이인듯

둘 다 O(n)