230126 TIL (알고리즘, 테스트코드)

알고리즘

과일 장수

코딩테스트 연습 - 과일 장수

프로그래머스

java-algorithm/Solution.java at main · jk891113/java-algorithm

GitHub - jk891113/java-algorithm

나의 풀이

과일 장수의 수익을 극대화 하기 위해서 한 박스에 들어 있는 과일 중 가장 낮은 점수로 모든 박스 내의 과일의 가격이 측정 되므로 가장 높은 점수의 과일들을 먼저 한 박스 내에 넣어 수익을 극대화 시키고 낮은 점수들의 과일을 나중에 넣거나 버리므로써 낮은 점수를 나중에 추가하거나 포기하여야 하기 때문에 정렬이 필요하다는 것은 단번에 느꼈다.

조금 더 괜찮은 방법이 없을까 고민하다가 딱히 다른 방법이 생각이 나지 않아서 그냥 흘러가는 대로 코드를 작성하였다.

public int solution(int k, int m, int[] score) {
    int answer = 0;
    if (score.length < m) return answer;
    Arrays.sort(score);

List<Integer> box = new ArrayList<>();
    for (int i = score.length - 1; i >= 0; i--) {
        int min = score[i];
        box.add(min);
        k = Math.min(k, min);
        if (box.size() == m) {
            answer += k * m;
            box.clear();
        }
    }
    return answer;
}

배열을 오름차순으로 정렬하였기 때문에 반복문을 뒤에서 부터 box 리스트에 넣어주고 해당 박스의 사이즈가 m과 같아지면 가장 낮은 점수를 k에 담아 k와 한 박스당 수량인 m을 곱하여 answer에 넣어주는 것을 반복하였다.

정답은 맞았지만 시간이 조금 오래 걸리는 것을 보고 그렇게 효율적이지 않다는 것을 느끼고 다른 사람의 풀이를 찾아보았는데 역시나 조금 더 괜찮은 방법이 있었다.

다른 사람의 풀이

박스 내의 최소 값만 반복문으로 찾아내어 한박스당 개수인 m을 곱하여 answer에 넣어주는 방법인 듯 하다.

public int solution(int k, int m, int[] score) {
    int answer = 0;
    Arrays.sort(score);

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

반복문 시작점을 점수가 가장 높은 박스의 가장 낮은 과일 점수인 score의 length - m 으로 설정하고 m만큼 차감하여 반복문을 박스 수량만큼만 반복할 수 있게 만들고, 해당 박스의 가장 작은 점수(score[i])를 박스당 과일 수량 m과 곱하여 answer에 넣어주는 방식인듯 하다.

확실히 모든 과일의 점수를 반복하는 것보다 박스의 수량만큼만 반복하는 것이 효율적인 것 같다.

---