[Algorithm] 이코테 : 두 배열의 원소 교체

 

시간복잡도를 잘못 계산했나?

왜 계수 정렬이 더 좋아보이지..

 

"""
문제: 배열A의 모든 원소의 합이 최대가 되도록 하라.
최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값
(1<=N<=100000, 1<=K<=N)

1. 아이디어 
(1) 계수 정렬
- A, B 오름차순 정렬
(2) python 내장 함수 sort
- A : 오름차순 정렬
- B : 내림차순 정렬

- k번 for문 돌면서, A가 B보다 작을 때 A의 가장 작은 원소 <-> B의 가장 큰 원소

2. 시간복잡도
(1) 계수 정렬
- A, B 정렬 : O(N+R)=10만+10만=20만 << 2초
- 원소 바꿔치기 : O(K)=10만
(2) python 내장 함수 sort
- A, B 정렬 : O(NlogN)=10만xlog10만=200만 << 2초
- 원소 바꿔치기 : O(K)=10만

3. 자료구조
A, B : int[][]

"""
""" input
5 3
1 2 5 4 3
5 5 6 6 5
"""
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
arrayA = list(map(int, input().split()))
arrayB = list(map(int, input().split()))

# 1. 계수정렬
def countingSort(array):
    count = [0]*(max(array)+1)
    result = []
    for i in array:
        count[i] += 1
    for i in range(len(count)):
        for j in range(count[i]):
            result.append(i)
    return result

for i in range(K):
    # A < B 일때만 교체
    if arrayA[i] < arrayB[N-i-1]:
        arrayA[i], arrayB[N-i-1] = arrayB[N-i-1], arrayA[i]

arrayA = countingSort(arrayA)
arrayB = countingSort(arrayB)


# 2. python 내장 함수 sort
arrayA.sort()
arrayB.sort(reverse=True)

for i in range(K):
    # A < B 일때만 교체
    if arrayA[i] < arrayB[i]:
        arrayA[i], arrayB[i] = arrayB[i], arrayA[i]
    else:
        break

print(sum(arrayA))

 

 

참고 - https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4