[그리디 알고리즘] ▲ 1744번 - 수 묶기

[백준] 1744번 - 수 묶기

(풀이1) 양수, 음수 리스트로 입력받아 계산하기

1) 문제 해결 아이디어

여기서는 처음부터 양수, 음수 2개의 리스트로 나누어 입력을 받고 이후에 계산을 하는 방식이다.

아이디어는 쉽게 떠올렸으나 주어진 테스트 케이스에서는 결과값이 제대로 나왔으나 나머지 테스트 케이스에 대해 오답이 나와 설계 오류를 찾는데 시간이 조금 걸렸다.

 

여기서 묶는 다는 것은 두 값을 곱한다는 뜻이고

묶지 않는다는 것은 두 값을 더한다는 뜻이다.

 

<수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게하는 방법>

1. 양수끼리 묶기(양수는 내림차순 정렬하여 순서대로 양수끼리 곱셈)

2. 음수끼리 묶기(음수는 오름차순 정렬하여 순서대로 음수끼리 곱셈)

3. 0은 음수와 묶기(0은 음수와 곱셈)

4. 양수, 음수 묶지 않기(양수와 음수는 덧셈)

 

첫번째 오류. 1에 대한 처리

두 수 중 1개라도 1이면 묶지 안아야한다.

두 수 중 1개라도 1이면 곱셈을 하는 것보다 덧셈을 하는 것이 더 큰 값을 만든다.

 

두번쨰 오류. 인덱스 범위에 대한 처리

마지막 인덱스의 경우 한 개의 값만 더해주어야 한다.

해당 리스트의 길이가 홀수, 짝수인지에 따라 마지막으로 검사할 수가 1, 2개로 달라진다.

2개가 남으면 기존코드처럼 i와 (i + 1) 인덱스 값을 모두 접근할 수 있지만

1개가 남으면 i 인덱스 값만 접근해야 한다.

길이가 홀수이면 마지막 검사할 값이 1개로 마지막 인덱스(n - 1)일 때

i + 1 인덱스가 (n)이 되므로 리스트 범위를 벗어나는 경우가 생긴다.

 

2) 소스코드

n = int(input())  # 수열 크기
arr = [int(input()) for _ in range(n)]  # 수열
arr.sort(reverse=True)  # 내림 차순 정렬
n_idx = -1  # 0 혹음 음수 시작 인덱스
negative = []
positive = []
sum = 0
for i in range(n):
  # 0보다 작거나 같은 인덱스 구하기
  if(arr[i] <= 0):
    n_idx = i
    break
    
# 양수가 없으면 
if(n_idx == 0):
  negative = arr[0: n]
elif(n_idx == -1):
  positive = arr[0: n]
else:
  positive = arr[0: n_idx]
  negative = arr[n_idx: n]

negative.sort(reverse=True)  # 내림차순 정렬

if(len(positive) == 0):
  # 음수의 합
  for i in range(0, len(negative), 2):
    # 마지막 인덱스이면
    if(i == len(negative) - 1):
      sum += negative[i]
    else:
      sum += negative[i] * negative[i + 1]
elif(len(negative) == 0):
  # 양수의 합
  for i in range(0, len(positive), 2):
    # 마지막 인덱스이면
    if(i == len(positive) - 1):
      sum += positive[i]  
    else:
      sum += (positive[i] * positive[i + 1])
else:
  # 양수의 합
  for i in range(0, len(positive), 2):
    # 마지막 인덱스이면
    if(i == len(positive) - 1):
      sum += positive[i]  
    else:
      sum += positive[i] * positive[i + 1]
  # 음수의 합
  for i in range(0, len(negative), 2):
    # 마지막 인덱스이면
    if(i == len(negative) - 1):
      sum += negative[i]
    else:
      sum += negative[i] * negative[i + 1]
  
print(sum)

 

 

(풀이2) 하나의 리스트로 입력받은 후 분리하여 계산하기

1) 문제 해결 아이디어

여기서는 입력은 한 개의 리스트(arr)로 받고 이후 한개씩 분리하며 계산을 하는 방식이다.

입력받은 것을 다시 검사하기 때문에 위 코드보다 약간 비효율적인 면이 있다.

 

2) 소스코드

n = int(input())  # 수열 크기
arr = [int(input()) for _ in range(n)]  # 수열
arr.sort(reverse=True)  # 내림 차순 정렬
sum = 0
n_idx = 50  # 0/음수 시작 인덱스

for i in range(0, n, 2):
  # 수열 크기가 1이거나 마지막 인덱스이면
  if(n == 1 or i > n -2):
    sum += arr[i]
    break
  
  # 둘다 양수이면
  if(arr[i] > 0 and arr[i + 1] > 0):
    # 둘 중 하나라도 1이면
    if(arr[i] == 1 or arr[i + 1] == 1):
      sum += (arr[i] + arr[i + 1])
    # 둘 다 1이 아니면
    else:
      sum += (arr[i] * arr[i + 1])
  # 첫번째 값만 0보다 크면
  elif(arr[i] > 0 and arr[i + 1] <= 0):
    sum += arr[i]  # 첫번째 값만 더하기
    n_idx = i + 1  # 0/음수 시작 인덱스 설정
    break
  # 둘다 음수이면
  elif(arr[i] <= 0):
    n_idx = i
    break

# 0/음수가 1개라도 있으면
if(n_idx != 50):
  arr = sorted(arr[n_idx:])  # 오름차순 정렬

  # 음수 합
  for i in range(0, len(arr), 2):
    # 맨 마지막 인덱스이면
    if(i == (len(arr) - 1)):
      sum += arr[i]
    else:
      sum += arr[i] * arr[i + 1]
  
print(sum)