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문 한번 더 쓰지 않고 그냥 한번에 계산까지 끝내버림
'코딩테스트-알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Lv.0] 정수를 나선형으로 배치하기 (1) | 2024.01.11 |
---|---|
[프로그래머스/Lv.1] 덧칠하기 (1) | 2024.01.09 |
[프로그래머스/Lv.1] 카드 뭉치 (0) | 2023.12.26 |
[프로그래머스/Lv.1] 명예의 전당 (1) (2) | 2023.12.22 |
[프로그래머스/Lv.1] 콜라 문제 (0) | 2023.12.22 |