Ch03. 정렬 알고리즘 (feat. 이것이 취업을 위한 코딩테스트다) (2)

나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다.

(내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)

 

https://jjuke-brain.tistory.com/71

Ch03. 정렬 알고리즘 (feat. 이것이 취업을 위한 코딩테스트다) (1)

 

이전 내용에 이어, 정렬 알고리즘 예제를 풀어보자.

 

 

목차

 

 

 

5. 4가지 정렬 알고리즘 비교

 

앞서 다루었던 네 가지 정렬 알고리즘을 비교하면 다음과 같다.

 

정렬 알고리즘 비교

 

참고로, 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 \( O(N \log N) \) 복잡도를 보장하도록 설계되어있다.

파이썬의 경우, 병합 정렬을 기반으로 하는 하이브리드 방식의 정렬 알고리즘을 사용한다.

 

 

 

 

6. 정렬 예제 - 두 배열의 원소 교체

 

Q) 두 배열 A와 B가 있다. 두 배열은 N개 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라 두 원소를 서로 바꾸는 것이다.

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

N, K, 그리고 배열 A와 배열 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

• 예를 들어, N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 가정하자.
  • 배열 A = [1, 2, 5, 4, 3]
  • 배열 B = [5, 5, 6, 6, 5]
• 이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.
  1. 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
  2. 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
  3. 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기
• 세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.
  • 배열 A = [6, 6, 5, 4, 5]
  • 배열 B = [3, 5, 1, 2, 5]
• 이때 배열 A의 원소의 합은 26이며, 이것이 최댓값이다.

 

문제 조건은 다음과 같다.

• 입력 조건
  • 첫 번째 줄에 N, K가 공백을 기준으로 구분되어 입력된다. (1 ≤ N ≤ 100,000, 0 ≤ K ≤ N)
  • 두 번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
  • 세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
• 출력 조건
  • 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

 

• 입력 예시
  • 5 3
  • 1 2 5 4 3
  • 5 5 6 6 5
• 출력 예시
  • 26

 

 

 

 

1) 문제 해결 아이디어

 

핵심 아이디어는 매번 배열 A에서 가장 작은 원소를 골라 배열 B의 가장 큰 원소와 바꿔치기 하는 것이다.

 

A에 대해 오름차순 정렬, B에 대해 내림차순 정렬하여 두 배열의 원소를 첫 번째 인덱스부터 A의 원소가 B의 원소보다 작을 때 교체를 수행한다.

 

배열의 원소가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 \( O(N \log N) \)을 보장하는 정렬 알고리즘을 이용해야 한다.

 

 

 

(1) Python 코드

 

import sys

fin = sys.stdin.readline

n, k = map(int, fin().split())
a = list(map(int, fin().split())
b = list(map(int, input().split())

a.sort()
b.sort(reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]
    else:
        break

print(sum(a))

 

문제 해결 아이디어를 제대로 이해했다면 금방 이해할 수 있을 것이다.

 

 

 

(2) C++ 코드

 

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a, b; # vector library를 사용

bool compare(int x, int y) { // 원소 값이 더 클 경우 높은 우선순위 갖도록 (내림차순 정렬 위해)
    return x > y;
}

int main(void) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    sort(a.begin(), a.end()); // 오름차순 정렬
    sort(b.begin(), b.end(), compare); // 내림차순 정렬
    int result = 0;
    for (int i = 0; i < k; i++) {
        if (a[i] < b[i]) swap(a[i], b[i]); // 작을 때에만 교차
        else break;
    }
    for (int i = 0; i < n; i++) {
        result += a[i];
    }
    cout << result << endl;
    return 0;
}

 

로직은 파이썬과 같다.

compare 함수를 직접 선언하여 표준 라이브러리로 내림차순 정렬을 하는 방법을 알아두자.