[구름톤 챌린지] Day 15 과일 구매 (Java)

구름LEVEL

전체 코드는 맨 아래에 있습니다!

 

 

문제 설명

마트에서 팔고 있는 과일은 N 종류가 한 개씩 있고, 각 과일의 가격은 P, 그리고 과일을 먹었을 때 그 과일의 포만감은 C이다.

이 마트에서는 과일을 조각 단위로 구매하는 것이 가능하다.

가격이 P인 과일을 조각 단위로 구매하고자 할 경우, 이 과일을 P개의 조각으로 자른 뒤 그중 원하는 몇 개의 조각만을 구매할 수 있다.

이때 모든 조각의 가격은 1, 먹었을 때 얻을 수 있는 포만감은 C/P로 동일합니다.

 

플레이어가 K의 돈을 가지고, 주어진 금액 이내에서 과일들의 포만감 합이 가장 크게 되도록 과일을 선택하려고 합니다.

플레이어가 최적의 방법에 따라 과일을 구매했을 때, 구매한 과일들의 최대 포만감 합을 구해보자.

 

 

//입력
6 13 // n:과일의 개수, k: 플레이어가 가진 돈
2 8 //각 과일의 가격, 과일을 먹었을 때의 포만감
7 35
1 5
3 12
10 30
1 7

//출력
63 //구매한 과일들의 최대 포만감 합

---

T I P

• 과일은 조각 단위로 살 수 있다는 점에 유의해야 합니다.
• 그 과일 가격보다 내가 가진 돈이 적더라도 조각단위로 살 수 있습니다.
• 가진 돈으로 가장 큰 포만감을 얻어내기 위해서는 단위당 가장 큰 포만감을 주는 과일을 골라야 합니다.
• 따라서 단위당 포만감이 가장 큰 과일부터 선택해 나가는 Greedy(탐욕법) 알고리즘을 사용합니다.

 

풀이 과정

1. 주어진 변수들을 모두 저장해 줍니다.

n: 과일 개수, k: 가진 돈,  마트에 있는 과일들은 ArrayList <int []> 형으로 가격과 포만감을 같이 저장해 줍니다.

String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);//과일 개수
int k = Integer.parseInt(s[1]);//플레이어가 가진 돈

ArrayList<int[]> fruits = new ArrayList<>();//마트에 있는 과일
for(int i=0;i<n;i++){
    s = br.readLine().split(" ");
    fruits.add(new int[]{Integer.parseInt(s[0]),Integer.parseInt(s[1])});//과일가격, 포만감
}

 

2.  조각단위로 살 수 있기 때문에, 가장 큰 포만감을 얻기 위해서는 단위 가격당 포만감이 많은 순으로 사면됩니다.

과일들을 가격이 1일 때의 포만감을 기준으로 정렬을 해서, 그 순서대로 과일을 불러올 것입니다.

 

(과일 가격 1당 포만감 :(포만감) / (가격) -> 포만감은 항상 가격의 배수로 주어지기 때문에 double 형으로 고려 X)

//가격 1당 포만감이 많이 차는 순으로 과일 정렬
Collections.sort(fruits, (a,b)->b[1]/b[0] - a[1]/a[0]);

 

람다식으로 정렬 구현하는 방법

예를 들어, Arrays.sort(arr, (x, y) -> y-x);라고 주어졌을 때

내가 작성한 (x, y)를 매개변수로 하여  x(앞에 오는 숫자), y(뒤에 오는 숫자)입니다.

->  뒤의 값이 양수가 나오는지, 음수가 나오는지에 따라 정렬됩니다.

->뒤의 식을 계산한 값이 음수가 나오면 그대로 두고, 양수가 나오면 자리를 바꿔줍니다.

-> 뒤의 식이 지금 y-x이기 때문에 현재 x=7, y=3에서 y-x=-4이므로 자리를 바꾸지 않습니다.

 

뒤의 숫자로 넘어가서 

이때의 y-x는 4-3=1로 양수가 나오기 때문에 자리를 바꿔 [7, 4, 3, 6, 1]이 됩니다. 

...

 

 

이것을 반대로 생각해 본다면

람다식을 정렬에 직접 사용할 수 있게 됩니다.

 

Arrays.sort(arr, (x, y) -> x-y);

x-y가 양수일 때 배열에서 서로 자리를 바꾼다 -> x-y>0 -> x> y 일 때 서로 자리를 바꾼다는 말이 됩니다.

결과적으로는 x <=y가 성립하는 배열이 위와 같은 오름차순 배열로 정렬됩니다.

 

반대로도 마찬가지로

Arrays.sort(arr, (x, y) -> y-x);

y-x가 양수일 때 숫자가 서로 자리를 바꾼다 -> y-x>0 -> y> x 일 때 서로 자리를 바꾼다는 말로

위와 같은 내림차순 배열이 만들어집니다.

 

3. 단위 가격당 포만감이 큰 과일 순서대로 ->  가진 돈을 모두 쓸 때까지 얻을 수 있는 포만감을 구하면 됩니다.

반복문을 사용해서 과일을 하나씩 가져와 줍니다.

산 과일들의 포만감을 모두 더해 full에 저장한 뒤 출력해 줍니다.

long full=0;//포만감 -> K, P, C 모두 정수 범위가 크기 때문에 포만감을 Long형으로 구현해줘야 합니다.
for(int[] fruit: fruits){//for-each구문으로 fruits 리스트에서 값을 하나씩 가져와 fruit에 넣어줍니다.
    if(k==0) break;//돈을 모두 썼다면 반복문 종료.

    if(k>=fruit[0]){//만약 과일을 하나를 통째로 살 수 있다면 사기.
        k-=fruit[0];//(현재 가진 돈 = 현재 가진 돈 - 과일 가격)
        full+=fruit[1];//포만감 = 포만감 + 현재 과일의 포만감
        
    }else{//만약 과일을 통째로 살 수 없다면 -> 조각으로 사기
        full+=fruit[1]/fruit[0]*k; //(가격 1당 포만감) * (가지고 있는 가격:k)
        k=0;//사는 조각 갯수 ( 조각은 1원단위로 나눠져 있음.)
    }
}

System.out.println(full); //구매한 과일들의 최대 포만감 합

---

전체 코드

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]);//과일 개수
		int k = Integer.parseInt(s[1]);//플레이어가 가진 돈
		
		ArrayList<int[]> fruits = new ArrayList<>();//마트에 있는 과일
		for(int i=0;i<n;i++){
			s = br.readLine().split(" ");
			fruits.add(new int[]{Integer.parseInt(s[0]),Integer.parseInt(s[1])});//과일가격,포만감
		}
		//가격 1당 포만감이 많이 차는 순으로 과일 정렬
		Collections.sort(fruits, (a,b)->b[1]/b[0] - a[1]/a[0]);
		
		long full=0;//포만감 -> K, P, C 모두 정수 범위가 크기 때문에 포만감을 Long형으로 구현해줘야 합니다.
		for(int[] fruit: fruits){//for-each구문으로 fruits 리스트에서 값을 하나씩 가져와 fruit에 넣어줍니다.
			if(k==0) break;//돈을 모두 썼다면 반복문 종료.
			
			if(k>=fruit[0]){//만약 과일을 하나를 통째로 살 수 있다면 사기.
				k-=fruit[0];//(현재 가진 돈 = 현재 가진 돈 - 과일 가격)
				full+=fruit[1];//포만감 = 포만감 + 현재 과일의 포만감
				
			}else{//만약 과일을 통째로 살 수 없다면 -> 조각으로 사기
				full+=fruit[1]/fruit[0]*k; //(가격 1당 포만감) * (가지고 있는 가격:k)
				k=0;//사는 조각 갯수 ( 조각은 1원단위로 나눠져 있음.)
			}
		}
		System.out.println(full); //구매한 과일들의 최대 포만감 합
	}
}

---

후기

구름톤 챌린지 덕분에 매일매일 문제 푸는 감을 잊지 않고 풀고 있습니다!

매일 올라오는 코드를 보면서 한 번 더 공부하게 되네요!! 

다들 5일 남았으니까 파이팅 해요!! 👊 😎