두 배열의 원소 교체 - '이것이 코딩 테스트다 with 파이썬'

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

두 배열 A, B가 주어지고, 두 배열의 크기 N이 주어지고, 배열 A의 원소와 배열 B의 원소 하나씩 바꿔치기를 K번 할수 있습니다. K번 바꿔치기를 수행하고 배열 A의 합의 최대값을 구하는 문제 입니다.(상세한 조건은 책을 참고해 주세요.)

 

1. 접근

먼저, 굉장히 쉬은 정렬 문제라고 생각하고, 다음과 같이 접근을 시도 했습니다.

1. K번 반복 수행을 하면서

2. 배열 A, B를 정렬 하고

3. 배열 B의 원소값이 배열 A의 원소값 보다 크면 반복을 진행하고

4. 그렇지 않으면 반복문을 탈출 하도록 접근 했습니다.

import java.util.Arrays;

public class Page182 {
    //입력 예시
    //5 3
    //1 2 5 4 3
    //5 5 6 6 5
    //출력 예시
    //26
    // 1 <= N <= 1000000
    // 0 <= K <= N
    // 원소 <= 10000000
    public static void main(String[] args) {
        int N = 5, K = 3;
        int[] A = {1, 2, 5, 4, 3};
        int[] B = {5, 5, 6, 6, 5};
        System.out.print(new Page182().solution(N, K, A, B));
    }

    int solution(int N, int K, int[] A, int[] B){
        // A에서 가장 작은 값 뽑음
        // B에서 가장 큰 값 뽑음
        // 두 값 바꿈
        // K번 반복
        // A의 원소 총합 반환
        final int LAST_INDEX = N - 1;
        final int FIRST_INDEX = 0;

        // 총시간 복잡도 : 2000000*(1000000 log(1000000))
        // 시간 복잡도 : 1000000
        for (int i = 0; i < K; i++) {
            // 시간 복잡도 : O(1000000 log(1000000))
            Arrays.sort(A);
            // 시간 복잡도 : O(1000000 log(1000000))
            Arrays.sort(B);

            // A의 가장 작은 값
            int smallestWithA = A[FIRST_INDEX];
            // B의 가장 큰 값
            int biggestWithB = B[LAST_INDEX];

            if (smallestWithA > biggestWithB)
                continue;

            // 바꿔치기
            B[LAST_INDEX] = smallestWithA;
            A[FIRST_INDEX] = biggestWithB;
        }
        return Arrays.stream(A).sum();
    }
}

 

하지만, 위의 소스 코드의 총 시간 복잡도를 계산해 보니, 총시간 복잡도 : 2000000*(1000000 log(1000000)) 와 같이 굉장히 컸습니다. 여기서 java 8 의 Arrays.sort() 함수는 구현 정보를 확인해 보면, Dual-Pivot Quicksort 를 적용하요 시간 복잡도 : O(Nlog(N))을 보장 합니다. 따라서, 정렬을 한번만 수행 하도록 수정 하였습니다.

 

import java.util.Arrays;

public class Page182_2 {
    //입력 예시
    //5 3
    //1 2 5 4 3
    //5 5 6 6 5
    //출력 예시
    //26
    // 1 <= N <= 1000000
    // 0 <= K <= N
    // 원소 <= 10000000
    public static void main(String[] args) {
        int N = 5, K = 3;
        int[] A = {1, 2, 5, 4, 3};
        int[] B = {5, 5, 6, 6, 5};
        System.out.print(new Page182_2().solution(N, K, A, B));
    }

    int solution(int N, int K, int[] A, int[] B){
        // A에서 가장 작은 값 뽑음
        // B에서 가장 큰 값 뽑음
        // 두 값 바꿈
        // K번 반복
        // A의 원소 총합 반환
        int lastIndex = N - 1;
        int firstIndex = 0;

        // 시간 복잡도 : O(1000000 log(1000000))
        Arrays.sort(A);
        // 시간 복잡도 : O(1000000 log(1000000))
        Arrays.sort(B);

        // 시간 복잡도 : 1000000
        for (int i = 0; i < K; i++) {
            // A의 가장 작은 값
            int smallestWithA = A[firstIndex];
            // B의 가장 큰 값
            int biggestWithB = B[lastIndex];

            if (smallestWithA < biggestWithB) break;

            // 바꿔치기
            B[lastIndex] = smallestWithA;
            A[firstIndex] = biggestWithB;

            firstIndex = firstIndex + 1;
            lastIndex = lastIndex - 1;
        }
        return Arrays.stream(A).sum();
    }
}

정렬을 한번만 시도하고, 각 배열의 인덱스 값을 업데이트 시켜주면서, 최대값과 최소값을 바꿔치기 해줍니다. 여기서 배열 B의 최대값을 찾기위해서 정렬후 마지막 인덱스의 접근하여 사용하였지만, int[] -> Integer[] 으로 정의 한다면, Arrays.sort(Integer[], Collections.reverseOrder())를 사용하여 거꾸로 정렬 할 수도 있습니다.