[프로그래머스]과일장수

이거 초반에 잘못 생각해서 쓸데없이 힘들게 푼 문제...

문제 주소

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

프로그래머스

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

• 한 상자에 사과를 m개씩 담아 포장합니다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

• (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
  • 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

---

입출력 예

k m score result

3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

---

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과 상자 가격

[1, 1, 2]	1 x 3 = 3
[2, 2, 2]	2 x 3 = 6
[4, 4, 4]	4 x 3 = 12
[4, 4, 4]	4 x 3 = 12

따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

 

풀이과정

일단 score.length/m → 박스 개수

score안의 것 k부터 줄세워서 박스개수만큼 카운트하면 될 거 같음

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int [] scoreCount = new int[k];
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] += 1;
        }
        int remained = 0;
        for(int i = scoreCount.length-1; i>=0;i--){
            answer += (scoreCount[i]/m)*i;
            remained = scoreCount[i]%m;
        }
        return answer;
    }
}

테스트 1입력값 〉3, 4, [1, 2, 3, 1, 2, 3, 1]기댓값 〉8실행 결과 〉실행한 결괏값 0이 기댓값 8과 다릅니다.테스트 2입력값 〉4, 3, [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]기댓값 〉33실행 결과 〉실행한 결괏값 7이 기댓값 33과 다릅니다.

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int [] scoreCount = new int[k];
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
        }
        int remained = 0;
        for(int i = scoreCount.length-1; i>=0;i--){
            answer += (scoreCount[i]/m)*i;
            remained = scoreCount[i]%m;
        }
        //남아있는거 다음에 안 더해주면 어떡하는데
        return answer;
    }
}

지금보니 remained를 써먹고있지 않음

아 그리고 remained가 1개라서 m=4고 1개 1개 2개 이렇게 남은 경우 커버가 안 됨

풀박스가 아니면 롤백해야하는데 deepcopy해?

걍 remainedIdx 옮기면 앞으로 안 읽겠단 소리, answer대신에 sum에다 더했다가 맞으면 넣고 아니면 안 넣음

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int [] scoreCount = new int[k];
        int [] remained = new int[k];
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
        }

        int remainedIdx = 0;
        for(int i = scoreCount.length-1; i>=0;i--){
            if(i!=scoreCount.length-1){
                int size = m;
                int sum = 0;
                if(remainedIdx>i){
                    for(int j = remainedIdx; j > i ; j--){//j--하면서 남아있는데부터 풀박스 만들어봄
                        sum += remained[j]*(scoreCount[j]);
                        if(size-remained[j]>=0){
                            sum += ((size-remained[j])*scoreCount[j]);
                            size = size - remained[j];  
                        }else{
                            sum += ((size)*scoreCount[j]);
                            size = 0;
                        }
                        if(size == 0){
                            answer = answer + sum;
                            remainedIdx = j-1;
                        }
                    }
                }
                
            }//풀박스가 아니면 롤백해야하는데 deepcopy해? 걍 remainedIdx 옮기면 앞으로 안 읽겠단 소리, answer대신에 sum에다 더했다가 맞으면 넣고 아니면 안 넣음
            answer += (scoreCount[i]/m)*i;
            remained[i] = scoreCount[i]%m;
            if(remainedIdx<i){remainedIdx = i;}
            
        }
        return answer;
    }
}

테스트 1입력값 〉3, 4, [1, 2, 3, 1, 2, 3, 1]기댓값 〉8실행 결과 〉실행한 결괏값 12이 기댓값 8과 다릅니다.테스트 2입력값 〉4, 3, [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]기댓값 〉33실행 결과 〉실행한 결괏값 7이 기댓값 33과 다릅니다.

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int [] scoreCount = new int[k];
        int [] remained = new int[k];
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
        }

        int remainedIdx = 0;
        for(int i = scoreCount.length-1; i>=0;i--){
            if(i!=scoreCount.length-1){
                int size = m;
                int sum = 0;
                if(remainedIdx>i){
                    for(int j = remainedIdx; j > i ; j--){//j--하면서 남아있는데부터 풀박스 만들어봄
                        sum += remained[j]*(scoreCount[j]);
                        if(size-remained[j]>=0){
                            sum += ((size-remained[j])*scoreCount[j]);
                            size = size - remained[j];  
                        }else{
                            sum += ((size)*scoreCount[j]);
                            size = 0;
                        }
                        if(size == 0){
                            answer = answer + sum;
                            System.out.println("answer"+ answer);
                            remainedIdx = j-1;
                            System.out.println("remainedIdx"+ remainedIdx);
                        }
                    }
                }
                
            }//remainedIdx 옮기면 앞으로 안 읽겠단 소리, answer대신에 sum에다 더했다가 맞으면 넣고 아니면 안 넣음
            answer += (scoreCount[i]/m)*i;
            System.out.println("(scoreCount[i]/m)*i;"+ (scoreCount[i]/m)*i);
            remained[i] = scoreCount[i]%m;
            System.out.println("scoreCount[i]%m;"+ scoreCount[i]%m);
            if(remainedIdx<i){remainedIdx = i;}
            System.out.println("remainedIdx"+ remainedIdx);
            System.out.println("answer"+ answer);
            
        }
        return answer;
    }
}

if(i!=scoreCount.length-1){

여기가 하나도 안 돌아갔는디

바꿔봄

if(remainedIdx<i){remainedIdx = i;} → if(remainedIdx==0){remainedIdx = i;}

이게 또 안돌아간듯

---

걍 remained for문 돌면서 걍 0으로 해버릴래 ㅋㅋㅋㅋㅋㅋ

다시 찬찬히 살펴봄 코드를

sum += ((size-remainedCopy[j])*scoreCountCopy[j]);

→

sum += ((size-remainedCopy[j])*(j+1));

로 수정함 가격이 j+1이어서

else{
                        sum += ((size)*scoreCountCopy[j]);

여기서도 잘못 곱하던거 수정함

sum += ((size)*(j+1));

근데 코드 보다보니 scoreCount가 하는 역할이 없어서 remained배열없애고 scoreCount에다 그냥%해서 남은 갯수 저장하기로 함

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        int [] scoreCount = new int[k];
        int [] scoreCountCopy = new int[k];
        //score당 몇개 있는지 세봄
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
            scoreCountCopy[score[i]-1] = scoreCountCopy[score[i]-1] + 1;
            System.out.println("scoreCount["+ (score[i]-1)+"]: "+ scoreCount[score[i]-1]);
        }
        int remainedIdx = scoreCount.length-1;
        for(int i = scoreCount.length-1; i>=0;i--){

            answer += (scoreCount[i]/m)*(i+1);
            scoreCount[i] = scoreCount[i]%m;
            scoreCountCopy[i] = scoreCount[i]%m;
            System.out.println("scoreCount["+ i+"]: "+ scoreCount[i]);
            System.out.println("answer"+ answer);
            
            int sum = 0;
            int size = m;

            for(int j = remainedIdx; j >= i ; j--){
                if(size>=scoreCountCopy[j]){
                    sum += ((size-scoreCountCopy[j])*(j+1));
                    size = size - scoreCountCopy[j];
                    scoreCountCopy[j]=0;
                    }else{//size<remainedCopy[j]
                        sum += ((size)*(j+1));
                        scoreCountCopy[j]=scoreCountCopy[j]-size;
                        size = 0;
                    }
                    if(size == 0){break;}
                }
                if(size == 0){
                    System.out.println("size0if "+ size);
                    answer = answer + sum;
                    for(int j = remainedIdx; j >= i ; j--){//맞다면 반영
                        scoreCount[j]=scoreCountCopy[j];
                    }
                    remainedIdx = i;
                }else{
                    System.out.println("size0else "+ size);
                    for(int j = remainedIdx; j >= i ; j--){//틀리다면 롤백
                        scoreCountCopy[j]=scoreCount[j];
                    }
                    
                }
            System.out.println("answer"+ answer);
        }
        return answer;
    }
}

 

print로 찍어봄

scoreCount[0]: 1

scoreCount[1]: 1

scoreCount[2]: 1

scoreCount[0]: 2

scoreCount[1]: 2

scoreCount[2]: 2

scoreCount[0]: 3

→

결과 :

scoreCount[2]: 2

scoreCount[1]: 2

scoreCount[0]: 3

m이 4개

scoreCount[2]: 2

answer0

size0else 2→ 롤백

answer0

scoreCount[1]: 2

answer0

size0if 0 → 2+2=4니까 풀박스 맞지

answer6 → 엥 32 +22 = 10인데 어 근데 정답이 8인데?

scoreCount[0]: 3

answer6

size0else 1

answer6

아니 여태까지 문제 잘못읽고 풀고있었음 ㅋㅋㅋㅋㅋㅋㅋㅋ

• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

나는 사과마다 가격 다른걸로 count 하고 있었는데 ㅋㅋㅋㅋㅋㅋㅋㅋ

사과마다 가격 다르게 sum 안 하고 그냥 answer에다 일괄 낮은가격으로 넣어봄

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        int [] scoreCount = new int[k];
        int [] scoreCountCopy = new int[k];
        //score당 몇개 있는지 세봄
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
            scoreCountCopy[score[i]-1] = scoreCountCopy[score[i]-1] + 1;
            System.out.println("scoreCount["+ (score[i]-1)+"]: "+ scoreCount[score[i]-1]);
        }
        int remainedIdx = scoreCount.length-1;
        for(int i = scoreCount.length-1; i>=0;i--){

            answer += (scoreCount[i]/m)*(i+1);
            scoreCount[i] = scoreCount[i]%m;
            scoreCountCopy[i] = scoreCount[i]%m;
            System.out.println("scoreCount["+ i+"]: "+ scoreCount[i]);
            System.out.println("answer"+ answer);
            
            int size = m;

            for(int j = remainedIdx; j >= i ; j--){
                if(size>=scoreCountCopy[j]){
                    size = size - scoreCountCopy[j];
                    scoreCountCopy[j]=0;
                    }else{//size<remainedCopy[j]
                        scoreCountCopy[j]=scoreCountCopy[j]-size;
                        size = 0;
                    }
                    if(size == 0){
                        answer += (m*(j+1));
                        break;
                    }
                }
                if(size == 0){
                    System.out.println("size0if "+ size);
                    for(int j = remainedIdx; j >= i ; j--){//맞다면 반영
                        scoreCount[j]=scoreCountCopy[j];
                    }
                    remainedIdx = i;
                }else{
                    System.out.println("size0else "+ size);
                    for(int j = remainedIdx; j >= i ; j--){//틀리다면 롤백
                        scoreCountCopy[j]=scoreCount[j];
                    }
                }
            System.out.println("answer"+ answer);
        }
        return answer;
    }
}

테스트 1
입력값 〉3, 4, [1, 2, 3, 1, 2, 3, 1]
기댓값 〉8
실행 결과 〉테스트를 통과하였습니다.
출력 〉
scoreCount[0]: 1
scoreCount[1]: 1
scoreCount[2]: 1
scoreCount[0]: 2
scoreCount[1]: 2
scoreCount[2]: 2
scoreCount[0]: 3
scoreCount[2]: 2
answer0
size0else 2
answer0
scoreCount[1]: 2
answer0
size0if 0
answer8
scoreCount[0]: 3
answer8
size0else 1
answer8
!! 테스트 1은 통과함

테스트 2
입력값 〉4, 3, [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]
기댓값 〉33
실행 결과 〉실행한 결괏값 13이 기댓값 33과 다릅니다.
출력 〉
scoreCount[3]: 1
scoreCount[0]: 1
scoreCount[1]: 1
scoreCount[1]: 2
scoreCount[3]: 2
scoreCount[3]: 3
scoreCount[3]: 4
scoreCount[3]: 5
scoreCount[0]: 2
scoreCount[1]: 3
scoreCount[3]: 6
scoreCount[1]: 4

scoreCount[3]: 0 m=3, 6개들어있었음
answer8 -> 4*2 맞아, 어 근데 왜 가격이랑 m개수만 곱하고 m은 안 곱해주지?

size0else 3
answer8
scoreCount[2]: 0
answer8
size0else 3
answer8
scoreCount[1]: 1
answer10
size0else 2
answer10
scoreCount[0]: 2
answer10
size0if 0
answer13

가격이랑 m개수만 곱하고 m은 안 곱해줬다는 걸 깨달음

answer += (scoreCount[i]/m)*(i+1);

→

answer += m*(scoreCount[i]/m)*(i+1);

그랬더니 통과함

제출 코드

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        int [] scoreCount = new int[k];
        int [] scoreCountCopy = new int[k];
        //score당 몇개 있는지 세봄
        for(int i=0;i<score.length;i++){
            scoreCount[score[i]-1] = scoreCount[score[i]-1] + 1;
            scoreCountCopy[score[i]-1] = scoreCountCopy[score[i]-1] + 1;
        }
        int remainedIdx = scoreCount.length-1;
        for(int i = scoreCount.length-1; i>=0;i--){

            answer += m*(scoreCount[i]/m)*(i+1);
            scoreCount[i] = scoreCount[i]%m;
            scoreCountCopy[i] = scoreCount[i]%m;
            
            int size = m;

            for(int j = remainedIdx; j >= i ; j--){
                if(size>=scoreCountCopy[j]){
                    size = size - scoreCountCopy[j];
                    scoreCountCopy[j]=0;
                    }else{//size<remainedCopy[j]
                        scoreCountCopy[j]=scoreCountCopy[j]-size;
                        size = 0;
                    }
                    if(size == 0){
                        answer += (m*(j+1));
                        break;
                    }
                }
                if(size == 0){
                    for(int j = remainedIdx; j >= i ; j--){//맞다면 반영
                        scoreCount[j]=scoreCountCopy[j];
                    }
                    remainedIdx = i;
                }else{
                    for(int j = remainedIdx; j >= i ; j--){//틀리다면 롤백
                        scoreCountCopy[j]=scoreCount[j];
                    }
                }
        }
        return answer;
    }

근데 나 이거 완전 이상하게 푼거임...

그냥 score를 sort해서 앞부터 m개씩 자르면 됨...

scoreCount 배열에 집어넣으면서 일이 엄청 복잡해짐...

다른 사람의 풀이

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;
    }
}