[BOJ][Python] 1026번 - 보물[정렬- 실버 4티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 보물

링크: 보물

문제설명

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

예제 입력 1

5
1 1 1 6 0
2 7 8 3 1

예제 출력

18

즉, 2개의 리스트를 하나는 오름차순, 다른 하나는 내림차순으로 정렬을 진행한 후 두 수를 곱해주면 해결이 될거같다.

여기서 주의할 점은 항상 위의 리스트가 값이 작다는 보장이 없다. 

그러기 때문에 두 리스트의 전체 합을 먼저 구한 후 어떤 리스트를 오름차순으로 정렬하고, 내림차순으로 정렬할지 부터 정해야한다.

 

📃 소스코드 및 설명

n = int(input())
numbers = list(map(int, input().split()))
numbers_2 = list(map(int, input().split()))

# 두 리스트의 합을 비교했을때 리스트의 크기가 큰 리스트를 찾는다
# (A>B) - (A<B) => A를 기준으로 A보다 B가 크면! 음수, 같으면 0 A가 크면 양수를 리턴한다.
compare_AB = (sum(numbers) > sum(numbers_2)) - (sum(numbers) < sum(numbers_2))


def mutipleList(descending, ascending):
  result = 0
  # Zip을 통해서 두개의 리스트를 곱해서 누적한 후 리턴!
  for a, b in zip(descending, ascending):
    result += a*b
  return result

if compare_AB == -1:  
  # 첫번째 리스트가 두번째 리스트의 합보다 작은 경우! 
  # 첫번째 리스트를 오름차순으로, 두번째 리스트를 내림차순으로 정렬!
  descending = sorted(numbers)
  ascending = sorted(numbers_2,reverse=True)
  
  print(mutipleList(descending, ascending))
  
elif compare_AB == 1:
  # 첫번째 리스트가 두번째 리스트의 합보다 큰 경우! 
  # 첫번째 리스트를 내림차순으로, 두번째 리스트를 오름차순으로 정렬!
  descending = sorted(numbers_2)
  ascending = sorted(numbers,reverse=True)
  print(mutipleList(descending, ascending))
else:
  # 첫번째 리스트와 두번째 리스트의 합이 동일할 경우 두 리스트중 가장 큰 값을 비교해서
  # 가장 큰 값이 있는 리스트를 내림차순으로 그게 아닌 리스트를 오름차순으로
  if max(numbers) < max(numbers_2):
      descending = sorted(numbers)
      ascending = sorted(numbers_2,reverse=True)
      print(mutipleList(descending, ascending))
  else:
    descending = sorted(numbers_2)
    ascending = sorted(numbers,reverse=True)
    print(mutipleList(descending, ascending))

뭔가 코드가 길어졌는데, 여기서 N값은 사용하지 않았다...

더 좋은 방식이 있을거같아서 다른사람의 풀이를 참고해보겠다.(아! 나중에 알고보니, 두번째 리스트는 재배열하면 안되는 거였다.....!!!)ㅠㅠㅠㅠㅠㅠㅠ 문제를 너무 대충 읽었다,..,ㅠ

 

📃 소스코드 및 설명

n = int(input())
numbers = list(map(int, input().split()))
number_2 = list(map(int, input().split()))
numbers.sort()

result = 0

for i in range(n):
  # x의 값은 위에서 이미 sort를 통해서 정렬을 했기 때문에 맨 앞쪽부터 계산해 나가면 된다.
  x = numbers[i]
  
  # 두번째 리스트 값중 가장 큰값의 index를 찾아서 pop시키고 두 값을 곱해준다.
  y = numbers_2.pop(numbers_2.index(max(numbers_2)))
  
  result += x * y
  
print(result)

 

* 문제를 조금만더 세세하게 읽고 주의해야겠다..ㅠㅠ