[이것이 코딩 테스트다 with Python]_25_정렬 알고리즘 비교 & 문제 풀이

220208 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=_kdE7ykab4Q&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=25 

 

 

 

 

 

 

1.  정렬 알고리즘 비교

: 최악의 경우에도 O(NlogN) 은 보장!

 

 

 

 

2. 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 배열에 10,000 정수 삽입
array = []

for _ in range(10000) :
    # 1~100 랜덤 정수
    array.append(randint(1, 100))

# 시간 재기
start_time = time.time()

# 선택 정렬 소스코드
for i in range(len(array)) :
    min_index = i
    for j in range(i+1, len(array)) :
        if array[min_index] > array[j] :
            min_index = j
    
    array[i], array[min_index] = array[min_index], array[i]

# 측정 종료
end_time = time.time()
# 수행 시간
print("선택 정렬 성능 측정 : ", end_time - start_time)


# 배열 다시 초기화
array = []

for _ in range(10000) :
    # 1~100 랜덤 정수
    array.append(randint(1, 100))

# 시간 재기
start_time = time.time()

# 기본 정렬 라이브러리
array.sort()

# 측정 종료
end_time = time.time()

# 수행 시간
print("기본 정렬 라이브러리 성능 측정 : ", end_time - start_time)

 

 

 

 

 

< 문제1 > 두 배열의 원소 교체

: 두개의 배열 A, B ( 모두 자연수 )

: 최대 K번 바꿔치기 연산 가능

: 바꿔치기 연산이란, 배열 A에 있는 원소 하나와 배열 B에 있는 원소를 서로 바꾸는 것

: 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 ㄱㄱ

: N, K, A와 B 배열이 주어졌을 때 최대 K 번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A 의 모든 원소의 합 최대값 출력

 

1) 매번 배열 A에서 가장 작은 원소, 배열 B에서 가장 큰 원소와 교체

2) A 에 대해서 오름 차순, B 에 대해서 내림 차순

3) 첫 번째 인덱스와 차례대로 확인하면서, A의 원소가 B의 원소보다 작을 때만 교체 수행

 

 

• python

n, k = map(int, input().split())

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

a.sort()    # 오름차순
b.sort(reverse = True)    # 내림차순

for i in range(k) :
    if a[i] < b[i] :    # A 원소가 B 원소보다 작으면
        # 교체
         a[i], b[i] = b[i], a[i]
    else :
        break

print(sum(a))
print(a)
print(b)

• c++

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a, b;

bool compare(int x, int y) {
    return x > y;
}

int main(void) {
    // N과 K를 입력받기
    cin >> n >> k;
    // 배열 A의 모든 원소를 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    // 배열 B의 모든 원소를 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    // 배열 A는 오름차순 정렬 수행
    sort(a.begin(), a.end());
    // 배열 B는 내림차순 정렬 수행
    sort(b.begin(), b.end(), compare);

    // 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 
    for (int i = 0; i < k; i++) {
        // A의 원소가 B의 원소보다 작은 경우
        if (a[i] < b[i]) swap(a[i], b[i]); // 두 원소를 교체
        // A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        else break;
    }

    // 배열 A의 모든 원소의 합을 출력
    long long result = 0;
    for (int i = 0; i < n; i++) {
        result += a[i];
    }
    cout << result << '\n';
}

• java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N과 K를 입력받기
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 배열 A의 모든 원소를 입력받기
        Integer[] a = new Integer[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        // 배열 B의 모든 원소를 입력받기
        Integer[] b = new Integer[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }

        // 배열 A는 오름차순 정렬 수행
        Arrays.sort(a);
        // 배열 B는 내림차순 정렬 수행
        Arrays.sort(b, Collections.reverseOrder());

        // 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 
        for (int i = 0; i < k; i++) {
            // A의 원소가 B의 원소보다 작은 경우
            if (a[i] < b[i]) {
                // 두 원소를 교체
                int temp = a[i];
                a[i] = b[i];
                b[i] = temp;
            }
            // A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
            else break;
        }

        // 배열 A의 모든 원소의 합을 출력
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += a[i];
        }
        System.out.println(result);
    }

}