[99클럽 코테 스터디] 19일차 TIL 그리디

 

 

오늘의 문제는 프로그래머스

 

과일 장수

 

 

문제

 

 

 

문제 설명 

 

k, m, socre가 주어졌을 때 과일 장수가 얻을 수 있는 최대 이익을 반환하는 문제입니다. 

사과는 1점 부터 k 점까지 상태에 따라 분류되고 점수가 높을 수록 품질이 좋은 사과입니다.

한 상자에 사과 m개를 담아 포장하고 가격은 상자에 담긴 사과 중 가장 점수가 낮은 사과의 점수(p) x m 입니다. 

 

입출력 예 

3, 4, [1, 2, 3, 1, 2, 3, 1]

8

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 25분이 걸렸습니다.

 

 

 

 

문제 접근 방식

주어진 점수 배열 score를 내림차순 정렬합니다. 정렬된 점수를 m개씩 묶어 각 묶음에서 마지막 점수를 리스트에 추가합니다. 이는 정렬된 상태에서 m번째 위치한 점수를 찾기 위한 것입니다. 

각 묶음의 최소 점수에 m을 곱한 값을 모두 더해 결과값을 반환합니다. 

 

 

 

 

문제 풀이

import java.util.Arrays; 
import java.util.ArrayList; 
import java.util.Comparator;

class Solution {
    public int solution(int k, int m, int[] score) {
        
        int answer = 0;
        int len = score.length;
        
        ArrayList<Integer> minScore = new ArrayList<>(); 
        
        Integer scores[] = Arrays.stream(score).boxed().toArray(Integer[]::new);
        Arrays.sort(scores, Comparator.reverseOrder());
        
        int index = m - 1; 
        
        for(int i = 0; i < (len/m); i++) {
            minScore.add(scores[index]);
            index += m; 
        }
        
        for(int i = 0; i < minScore.size(); i++) {
            answer += minScore.get(i) * m;
        }
        
        return answer;
    }
}

 

 

코드 개선하기

import java.util.Arrays; 
import java.util.Comparator;

class Solution {
    public int solution(int k, int m, int[] score) {
        
        int answer = 0;
        int len = score.length;
        
        Integer scores[] = Arrays.stream(score).boxed().toArray(Integer[]::new);
        Arrays.sort(scores, Comparator.reverseOrder());
        
        for(int i = m - 1 ; i < len; i += m) {
            answer += scores[i] * m;
        }
        
        return answer;
    }
}

 

개선된 코드 알아보기 

 

기존 코드는 각 묶음의 최소 점수를 저장하기 위해 ArrayList를 생성하고, 이를 사용해 최종 답을 계산하는 방식이었습니다. 그러나 이 과정은 불필요하기 때문에, 리스트를 제거하고 반복문 내에서 배열의 요소에 직접 접근하여 점수를 계산하도록 수정했습니다.

또한, 기존 코드에서는 점수를 계산하기 위해 또 다른 반복문이 실행됐었습니다. 개선된 코드에서는 이 반복문을 제거하고, 배열에 접근하면서 동시에 점수를 계산해 answer에 바로 더하도록 수정했습니다. 

 

 

 

그리디 알고리즘 알아보기 

 

그리디 알고리즘은 각 단계에서 최적이라고 생각되는 것을 선택해 나아가며 최종적인 해답에 도달하는 알고리즘입니다. 그리디 알고리즘은 각 부분에서의 최적 선택이 전체 문제의 최적 해를 보장하는 상황에서 쓰입니다. 

 

그리디 알고리즘의 단계는 다음과 같이 나뉩니다. 

 

1. 문제의 해를 구성할 부분적인 선택 기준 정의하기 

• 목표는 주어진 점수 배열에서 m개씩 묶어 각 묶음의 가장 작은 점수를 선택하고 그 점수에 m을 곱해 최대의 합을 구하는 것입니다.
• 선택 기준은 각 묶음에서 가장 작은 점수를 선택하는 것입니다.  

2. 현재 상황에서 최적의 선택 하기 

• 주어진 점수 배열을 내림차순으로 정렬합니다.
• 각 묶음에서 m번째로 작은 점수를 선택해 그 값을 최종 결과에 반환합니다. 

3. 이 선택이 최적의 해를 보장하는지 확인하기 

• 높은 점수를 먼저 처리해 각 묶음에서 최적의 선택을 하고 있습니다. 

 

 

 

 

int 형 배열을 Integer 배열로 변환하기 

자바의 기본형 배열인 int 배열은 Comparator를 사용해 내림차순으로 정렬할 수 없습니다. Comparator가 객체를 비교하기 때문에 int 배열을 Integer 배열로 변환해야 합니다. 

이 때 사용하는 것이 boxing 입니다. boxing은 기본형 데이터 타입을 그에 대응하는 객체 타입으로 변환합니다. 

Integer scores[] = Arrays.stream(score).boxed().toArray(Integer[]::new);
Arrays.sort(scores, Comparator.reverseOrder());

 

위의 코드를 자세히 살펴봅시다. 

먼저 Arrays.stream(score)를 통해 int 배열을 스트림으로 변환합니다. 

그리고 boxed()를 사용해 스트림의 각 int 값을 Integer 객체로 변환합니다. 

마지막으로 toArray(Integer[]::new)를 통해 변환된 Integer 객체들을 Integer 배열 형태로 만들어줍니다. 

 

 

 

오름차순 정렬로 뒤에서 부터 접근하는 풀이 

아래 코드는 배열을 내림차순으로 정렬하는 대신 오름차순으로 정렬한 뒤 반복문을 역방향으로 실행하여 동일한 결과를 반환하는 식으로 작성된 코드입니다. 

이 장점은 배열을 Integer 객체 타입으로 변환하는 과정과 내림차순 정렬 과정을 생략하여 더 직관적이고 효율적으로 구현된다는 것입니다. 

 

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int len = score.length;

        Arrays.sort(score);
        
        for (int i = len - m; i >= 0; i -= m) {
            answer += score[i] * m;
        }

        return Math.max(answer, 0);
    }
}

• 오름차순 정렬 후 역방향 접근 : 점수 배열을 오름차순으로 정렬한 후 배열의 끝에서부터 m 간격으로 거꾸로 접근해 점수를 선택합니다. 
• Integer 객체 변환 불필요 : 내림 차순 정렬 대신 단순한 오름차순 정렬만 사용해 더 직관적인 코드입니다. 

 

 

 

 

 

이렇게 오늘 19일차 TIL을 작성해 보았습니다.