블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 1026번: 보물을 풀고 작성한 글입니다.
문제
설명
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
출력
첫째 줄에 S의 최솟값을 출력한다.
풀이
접근법
배열 A 와 B 를 각각 오름차순과 내림차순 또는 내림차순과 오름차순으로 정렬의 순서를 바꾸어 정렬한 다음 각각의 요소를 for 반복문을 활용해 곱해서 더해주는 방법을 생각했다.
문제는 설명에 나와있는 B에 있는 수는 재배열하면 안 된다 는 문장이었다. 하지만 질문 페이지를 확인해보니 이 부분은 문제를 푸는 데 있어 무시해도 괜찮은 조건이라는 서술이 나와 있어 결국 무시하고 풀었다.
나의 풀이
접근법을 토대로 아래와 같이 sorted() 내장함수를 활용해 하나의 배열은 오름차순으로, 다른 하나의 배열은 매개변수 reverse 의 값에 True 를 넘겨 내림차순으로 정렬하고 각각의 요소를 곱해주어 더해줬다.
N: int = int(input())
A: list[int] = list(map(int, input().split(" ")))
B: list[int] = list(map(int, input().split(" ")))
answer: int = 0
for A_num, B_num in zip(sorted(A), sorted(B, reverse=True)):
answer += (A_num * B_num)
print(answer)아래와 같이 SUM() 함수 및 리스트 컴프리헨션을 사용하여 훨씬 짧게 문제를 풀이할 수도 있다.
N: int = int(input())
A: list[int] = list(map(int, input().split(" ")))
B: list[int] = list(map(int, input().split(" ")))
print(sum([ A_num * B_num for A_num, B_num in zip(sorted(A), sorted(B, reverse=True)) ]))Big-O
파이썬 내장 함수 sorted() 의 시간 복잡도가 O(NlogN)이기 때문에 for 반복문에서 배열의 길이 N 만큼, 다시 말해 O(N)의 시간 복잡도가 들더라도 정렬 때문에 결국 Big-O는 O(NlogN)이다.
