[이.취.코] Chap 6. 정렬 - 두 배열의 원소 교체

1. 두 배열의 원소 교체

• 난이도
  • 하
• 풀이 시간
  • 20분
• 시간 제한
  • 2초
• 메모리 제한
  • 128MB
• 기출
  • 국제 알고리즘 대회

A. 문제

두 개의 배열 A와 B가 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.

배열 A의 원소와 배열 B의 원소를 최대 K번 바꿀 수 있다.

최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

a. 예를 들면.

N = 5, K = 3

A = [1, 2, 5, 4, 3] B = [5, 5, 6, 6, 5]

일때.

K(3)번 연산을 수행하여 아래와 같이 된다.

A = [6, 6, 5, 4, 5] B = [5, 1, 2, 3, 5]

여기서 A의 합은 26이다.

b. 입력 조건

• 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다.
  • 1 <= N <= 100,000
  • 0 <= K <= N
• 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다.
  • 모든 원소는 10,000,000보다 작은 자연수이다.
• 세 번째 줄에는 배열 B의 원소들이 공백으로 구분되어 입력된다.
  • 모든 원소는 10,000,000보다 작은 자연수이다.

c. 출력 조건

• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값.

d. 테스트 케이스

• 입력 예시

  
  5 3  
  1 2 5 4 3  
  5 5 6 6 5
  
  

• 출력 예시

  
  26
  
  

B. 내 답안

# n, k = list(map(int, input().split()))  
  
# A = list(map(int, input().split()))  
# B = list(map(int, input().split()))  
  
n, k = 5, 3  
  
A = [1, 2, 5, 4, 3]  
B = [5, 5, 6, 6, 5]  
  
A.sort()  
B.sort(reverse=True)  
  
print(A)  
print(B)  
  
for i in range(k):  
    A[i], B[i] = B[i], A[i]  
  
result = sum(A)  
  
print(result)

a. 회고

분석

빨리 풀어야지 하다가, 조건 하나를 빼먹었다. A의 최댓값을 구하는 것이라 A와 B를 교체할 때 B의 원소가 A의 원소보다 작으면 교체하지 않는다는 조건을 빼먹었다.

반성

쉬운 문제인데도 이렇게 틀리는 구나 싶었다. 조건을 똑바로 읽고 메모해야겠다.

C. 문제 해설

배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다.

단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행한다.

이런 과정을 K번 반복하면 정답을 얻을 수 있다.

배열 A의 원소를 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 정렬한다. 그리고 두 원소를 가장 첫 번째 인덱스부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다.

원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 알고리즘을 사용해야 한다.

a. 책 답안

python-for-coding-test/12.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #정렬 #두배열의원소교체