[프로그래머스/Lv.1] 과일 장수

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

 

 

 

틀린 코드

1

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int max = 0;
        ArrayList<Integer> apple = new ArrayList<>();
        ArrayList<Integer> box = new ArrayList<>();
        
        for(int n : score) apple.add(n);
        
        while(apple.size() > 0) {
            max = Collections.max(apple);
            apple.remove(Integer.valueOf(max));
            box.add(max);
            
            if(box.size() == m) {
                answer += Collections.min(box) * m;
                box.clear();
            } else continue;
        }
        
        
        return answer;
    }
}

 

시간 초과 

 

 

2

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int max = 0;
        ArrayList<Integer> apple = new ArrayList<>();
        ArrayList<Integer> box = new ArrayList<>();
        
        for(int n : score) apple.add(n);
        
        for(int i=0; i<score.length;i++){
            max = Collections.max(apple);
            apple.remove(Integer.valueOf(max));
            box.add(max);
            
            if(box.size() == m) {
                answer += Collections.min(box) * m;
                box.clear();
            } else continue;
        }     
        
        return answer;
    }
}

for문으로 돌게 고쳐보았는데 시간초과 하나 줄음,,, 시간초과 줄이는거 연구해보기

 

.

.

.

 

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int count = 0;
        int[] box = new int[score.length / m];
        Arrays.sort(score);
        
        
        for(int i = score.length - m; i >= 0; i -= m) {
            box[count] = score[i];
            count++;
        }
        
        
        for(int n : box) {
            answer += n * m;
        }
        
        return answer;
    }
}

 

시간 초과나는 이유를 생각해보다가 최고값 찾고 넣어주고 비워주고 하는 과정이 복잡한거같아서 줄여보려했다

여러가지 바꿔보다가 그냥 배열을 내림차순해서 m번째 해당되는거마다 값 저장해두고(내림차순했을때 m번째마다 자르면 박스에 들어가는 수 중 가장 작음) 나중에 그 값들만 계산에 넣으면 간단하게 풀릴거란게 떠올랐다

괜히 또 어렵게 생각하고 돌아돌아왔지만 이게 쌓이다보면 나중엔 간단하게 푸는 방법부터 떠오르게 되겠지? 하는 기대도 있다

 

아무튼 내림차순으로 해서 코드를 쓰고 돌렸는데 

Arrays.sort(score, Collections.reverseOrder());

 for(int i = m - 1; i < score.length; i += m) {

 

 

 

int형 배열은 내림차순 사용할 수 없음 Collections.reverseOrder()와 함께 쓸 수 없음

-> Integer 배열로 변환하는 과정이 필요함

 

그래서 오름차순으로 해준 후 배열 뒤에서부터 읽어오면서 m개씩 끊어서 마지막 값을 box 배열에 넣고 한꺼번에 계산하는걸로 바꿔주었다

 

.

.

 

다 풀고난 후 의문인건 k는 왜 주어지는걸까? 하는것이다 문제를 풀 때 전혀 쓸 일이 없는데 왜 주어졌을까 그냥 궁금하다 나만 그런가 해서 다른 사람 풀이도 봤는데 k를 이용한 사람이 없었다

 

그리고 완전 간단하게 코드를 적은 사람을 발견했는데

import java.util.*;

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

        Arrays.sort(score);

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

        return answer;
    }
}

 

이렇게 간단히 할 수 있다니 배워간다,, for문 한번 더 쓰지 않고 그냥 한번에 계산까지 끝내버림