JAVA 자료구조 (배열) - 배열 파티션 ⅰ

배열 파티션 ⅰ

오름차순 풀이

페어의 min()을 합산했을 때 최대가 되려면 결국 각각의 min() 조합이 가급적 머야 한다는 뜻이다. 

그림 7 - 10 min(a,b)의 합으로 최댓값을 만들 수 있는 조합

 

실제로 그림 7-10에서 하나씩 조합해보면 동일한 결과를 얻을 수 있다. 오름 차순으로 정렬된 상태에서 인접 엘리먼트 페어(Adjacent Elements Pair)를 만들면 가장 큰 a₁과 a₂ 페어들을 만들 수 있고 이 페어들의 min()의 합이 곧 만들 수 있는 최대 합이 된다. 

 

Pair의 min을 합하는 코드

public int solution(int [] nums) {
    Arrays.sort(nums);
    List<Integer> pair = new ArrayList<>();
    int sum =0;

    for(int n: nums){
        pair.add(n);
        //페어 변수에 값이 2개 채워지면 min을 합산하고 변수 초기화
        if(pair.size()==2){
            sum += Collections.min(pair);
            pair.clear();
        }
    }

   return sum;
}

 

풀이2 - 짝수 번째 값 계산

풀이1 처럼 페어에 대해 일일이 min()값을 구하지 않아도 짝수 번째 인덱스(인덱스는 0부터 시작한다.)의 값을 더하면 될거 같다. 정렬된 상태에서 짝수 번째에 항상 작은 값이 위치하기 때문이다. 불필요한 리스트 변수를 생략할 수 있기 때문에, 전체 코드 또한 많이 줄어들어 매우 간결하다.

public int solution(int [] nums) {
    Arrays.sort(nums);
    int sum = 0;

    for(int i = 0; i < nums.length; i++){
        if(i%2 == 0) sum+=nums[i];
    }

   return sum;
}

 

 

풀이	방식	실행시간
1	오름 차순 풀이	41밀리초
2	짝수 번째 값 계산	11밀리초

 

 

[출처 - 자바 알고리즘 인터뷰 with 코틀린 , 저 박상길]

https://www.onlybook.co.kr/entry/java-algorithm-interview

자바 알고리즘 인터뷰 with 코틀린