1. ๋ฌธ์ ์ค๋ช
2. ์ ๊ทผ ๋ฐฉ์
KEY WORD:
GREEDY Algorithm
๊ด๋ฌผ์ ์บ๋ ๋น์ฉ์ ์ต์ํ ํ๊ธฐ ์ํด์๋, ๋ ๊ณก๊ดญ์ด๋ก ์บค์ ๋, ๋น์ฉ์ด ์ ์ผ ๋ง์ด ๋๋ ๊ตฌ๊ฐ์ด ์์ ์ค๋๋ก, ๊ด๋ฌผ ๋ฆฌ์คํธ๋ฅผ ์ ๋ ฌํ๊ณ , ๊ตฌ๊ฐ๋ค์ ์ํํ๋ฉฐ, ๊ทธ๋ ๊ทธ๋ ์ต์ ์ ๊ณก๊ดญ์ด๋ก ์ผ์ฒ๋ฆฌ๋ฅผ ํด์ผํ๋ค.
๊ทธ ์๋ฏธ์์ Greedy Algorithm
์ ์จ์ผ ํ๋ ๊ฒ์ด๋ค.
๊ด๋ฌผ์ ํฌ๊ธฐ๊ฐ 50๋ฐ์ ์๋จ์ผ๋ก ์๊ฐ๋ณต์ก๋ ๊ด๋ จํด์ ๊ฑฑ์ ํ ๊ฒ์ ์์ ๊ฒ ๊ฐ๋ค. ๊ทธ๋ ๋ค๋ฉด ํด์ผํ ์ผ์,
- ๊ด๋ฌผ List๋ฅผ 5๊ฐ์ฉ ์๋ฅธ๋ค. ๊ทธ๊ฒ์ด ์ผ์ ๋จ์์ด๊ธฐ ๋๋ฌธ์ด๋ค.
(๊ทผ๋ฐ ๊ด๋ฌผ์ด 5์ ๋ฐฐ์๋ก ์ ๋ง์ ๋จ์ด์ง ์ ์๋ค. ๊ทธ๋ฌ๋ฉด ๋งจ ๋ง์ง๋ง์ 3๊ฐ๋ 4๊ฐ๊ฐ ํ๋์ ๋ฌถ์์ด ๋ ์๋ ์์์ผ๋ก ์ด๋ฅผ ์ฃผ์ํด์ Loop๋ฅผ ์ง ๋ค.) - ๋๋ ์ง ๊ด๋ฌผ ๋ฌถ์์
๋ ๊ณก๊ดญ์ด
๋ก ์์ ํ์ ๋ํผ๋ก๋
๊ฐ ๊ฐ์ฅ ๋ง์ด ๋๋ ์์ผ๋ก ์ ๋ ฌํ๋ค. - ์ด์ ๊ฐ์ง๊ณ ์๋ ๊ณก๊ดญ์ด ์ค์์
์ต์ ์ ๊ณก๊ดญ์ด
๋ฅผ ์ด์ฉํ์ฌ ์ฒซ ๊ตฌ๊ฐ๋ถํฐ ์์๋๋ก ์์ ํ๊ณ ํผ๋ก๋๋ฅผ ์ดํฉ ํ๋ค.
(โป ์ฃผ์์ : Loop๋ฌธ์ผ๋ก ํด๋น ๋ถ๋ถ์ ๊ตฌํํ ๋, ๊ณก๊ดญ์ด๋ฅผ ๋จผ์ ๋ค ์จ๋ฒ๋ฆฌ๊ฑฐ๋, ์์ ํ ๊ฒ์ด ๋จผ์ ๋๋๋ฒ๋ฆฌ๊ฑฐ๋, ํ๋ ๊ฒฝ์ฐ์ ๋ํ ์ ์ด ์ฅ์น๊ฐ ํ์ํ๋ค.)
3. ์ฝ๋ ๋ถ์
import java.io.*;
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
// 1. ๊ด๋ฌผ์ 5๊ฐ์ฉ ์๋ผ์ (๋งจ ๋ง์ง๋ง์ ๋ฑ๊ฐ ๋ผ๋ฆฌ) ๊ฐ ๊ณก๊ดญ์ด๋ก ํ์ ๋ cost๊ฐ ์ผ๋ง๋ ๋๋์ง ๊ณ์ฐ
// 2. ๋ ๊ณก๊ดญ์ด๋ก ์์
ํ์ ๋ ๋๋ ๋น์ฉ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ
// (ํด๋น ๊ธฐ์ค์ด ๊ฐ ๋จ์๋ณ ์ฝ์คํธ ์ฐจ์ด๊ฐ ๊ทน๋ช
ํ ๋ค์ด๋จ. + ๋ ๊ณก๊ดญ์ด๋ก cost๊ฐ ๋ง์ด ๋ ๋ค
// == ๋ค๋ฅธ ๊ณก๊ดญ์ด๋ค๋ก๋ cost๊ฐ ๋ง์ด ๋ ๋ค.)
// 3. ๊ณก๊ดญ์ด๋ฅผ ๋ค ์ฐ๊ฑฐ๋ ์๋๋ฉด, ๋์ ์ ๋ถ ์ฒ๋ฆฌํ๊ฑฐ๋ ํ ๋๊น์ง ์์
๋ฐ๋ณต
// (ํด๋น ๋จ์์์ ํผ๋ก๋๊ฐ ๊ฐ์ฅ ์ ๊ฒ ๋๋ ๊ณก๊ดญ์ด๋ฅผ ์ ์ ํ์ฌ ์ด๋ค.)
List<Mineral> stress = new ArrayList<>();
// ๋ชจ๋ ๊ณก๊ดญ์ด ์๋ฅผ ๋ํ๋ค.
int pick_cnt = Arrays.stream(picks).sum();
// ์ต๋ ์์
๋์ ๊ตฌํ๋ค. ์ธ ์ ์๋ ๊ณก๊ดญ์ด ์, ๊ด๋ฌผ๋ ์ค ์ ์ ์ชฝ์ด ์ต๋ ์์
๋์ด๋ค.
int work_cnt = Math.min(pick_cnt*5, minerals.length);
//๋ ๊ณก๊ดญ์ด๋ก ํ์ ๋, ๊ตฌ๊ฐ๋ณ ์ต๋ ์์
๋์ ๊ตฌํด ๋์ ๊ฒ์ด๋ค.
for(int i =0; i<work_cnt; i+=5){
int d_cost = 0;
int i_cost = 0;
int s_cost = 0;
for(int j = 0; j<5; j++){
int next = i+j;
// ์ค์! -> ์ต๋ ์์
๋์ ๋์ด๊ฐ ์ ๋ ์ด์ ๊ณ์ฐํ์ง ์๋๋ค!
// ๋งจ ๋ง์ง๋ง ๋ฌถ์์ด 1~4๊ฐ์ ๋ฑ๊ฐ๋ก ๋์ด์์ ๊ฒฝ์ฐ, ํด๋น break ๋ฌธ์ ํตํด ์ ์ ํ ํ์ถํ ์ ์๋ค!
if(next == work_cnt) break;
switch(minerals[next]) {
case "diamond": {
d_cost+=1;
i_cost+=5;
s_cost+=25;
break;
}
case "iron": {
d_cost+=1;
i_cost+=1;
s_cost+=5;
break;
}
case "stone": {
d_cost+=1;
i_cost+=1;
s_cost+=1;
break;
}
}
}
// ๊ฐ ๊ตฌ๊ฐ ๋ณ ๋ค์ด์, ์ฒ , ๋ ๊ณก๊ดญ์ด๋ก ์์
ํ์ ๋,
// ํผ๋ก๋๋ฅผ ๊ณ์ฐํด์, stress(ํผ๋ก๋) ๋ฆฌ์คํธ์ ์ ์ฅํ๋ค.
stress.add(new Mineral(d_cost, i_cost, s_cost));
}
// ๋ด๋ฆผ์ฐจ์(๋น์ฉ ๋ง์ด ๋๋ ๋ฌถ์ ์์ผ๋ก ์ ๋ ฌ)
Collections.sort(stress, (o1,o2) -> o2.s_cost - o1.s_cost);
int min_cost = 0;
for(int i =0; i< stress.size(); i++){
// ๊ณก๊ดญ์ด ๋ค ์ฐ๋ฉด ํ์ถ
if(picks[0] == 0 && picks[1] == 0 && picks[2] == 0) break;
// ๋ค์ด์ -> ์ฒ -> ๋ ๊ณก๊ดญ์ด ์์ผ๋ก ์ฌ์ฉ
if(picks[0] > 0) {picks[0]--; min_cost += stress.get(i).d_cost;}
else if(picks[1] > 0) {picks[1]--; min_cost += stress.get(i).i_cost;}
else if(picks[2] > 0) {picks[2]--; min_cost += stress.get(i).s_cost;}
}
// ํผ๋ก๋์ ์ดํฉ ๋ฐํ
return min_cost;
}
}
// ๊ตฌ๊ฐ ๋ณ, ๊ฐ ๊ณก๊ดญ์ด๋ก ์์
ํ์ ๋์ ํผ๋ก๋๋ฅผ ์ ์ฅํ๋ค.
class Mineral {
int d_cost;
int i_cost;
int s_cost;
public Mineral(int d, int i, int s){
this.d_cost = d;
this.i_cost = i;
this.s_cost = s;
}
}
4. ์ฑ์ฅํ๊ธฐ
ํด๋น ๋ฌธ์ ๋ ์ต๋ ๋น์ฉ์ผ๋ก ์ ๋ ฌ ํ, Greedy ์ฌ์ฉ ์ธ ๊ฒ์ ๋นจ๋ฆฌ catch ํ์ง๋ง,๊ตฌ๊ฐ์ ๋ฌถ์์ ๋ 5๊ฐ๊ฐ ๊ฝ ์ ์ฐจ๋ ๋ฌถ์์ ๋ํ ์ฒ๋ฆฌ
, ๊ณก๊ดญ์ด๊ฐ ๋จผ์ ๋์ด ๋ ๋, ํน์ ๊ด๋ฌผ์ ๋จผ์ ๋ค ์บ๋ฒ๋ ธ์ ๋
์ ๋ํ ์ฒ๋ฆฌ๊ฐ ๋ฏธํกํด์ ๋ฌธ์ ๋ฅผ ํ์ง ๋ชปํ๋ค.
ํ๋ก๊ทธ๋๋จธ์ค๋ ๋ฐฐ์ด index ์ด๊ณผ ์, ์ด๋์ ์ด๊ณผํ๋ค๊ณ ์ ๋ณด์ฌ์ค์ ๋ ์ฐพ๊ธฐ๊ฐ ํ๋ค์๋ค. ๊ทธ๋์ ์ธํ
๋ฆฌ์ ์ด์๋ค๊ฐ ๋ณต๋ถํด์ ๋ฌธ์ ๋ฅผ ์ฐพ์๋ค.
๋ด๊ฐ ๋๋ฌด ์ด๋ ต๊ฒ ๊ตฌํํ ๊ฒ์ด ํ๊ทผ์ธ ๊ฒ ๊ฐ๋ค.
int cost = 0;
int share = minerals.length/5;
int remainder = minerals.length%5;
int cost_length = remainder==0? share : share+1;
Cost [] allCost = new Cost [cost_length];
for(int i = 0; i < cost_length; i++) {
int d_cost = 0;
int i_cost = 0;
int s_cost = 0;
int loop_length = (i == cost_length-1)? remainder : 5;
for(int j = 0; j < loop_length; j++) {
switch(minerals[i*5+j]){
๋ณด๋ฉด ๋ชซ๊ณผ ๋๋จธ์ง๋ฅผ ์ด์ฉํด์ ํ๋ ค๊ณ ํ์๊ณ , ๊ตฌ๊ฐ ๋ณ ๊ฐ ๋ํ ๊ธธ์ด๊ฐ ์ ํด์ง ๋ฐฐ์ด์ ์ด์ฉํด์ ํ๋ ค๊ณ ํ์๋ค. ๋ฐฐ์ด์ ๊ธธ์ด๋ ๊ตฌ๊ฐ/5
๋๋จธ์ง๊ฐ ์์ผ๋ฉด ๊ตฌ๊ฐ/5 +1
๋ก ๋์๋ค. ๊ตณ์ด ๋ฐฐ์ด์ ์ ํํด์ ๋ฌธ์ ๋ฅผ ๋ ์ด๋ ต๊ฒ ๋ง๋ค์๋ค.
List๋ฅผ ์ฌ์ฉํ๋ฉด ์์ฒญ ๋๋ฆด ๊ฑฐ๋ผ๋ ๋ง์ฐํ ์๊ฐ์ด List ์ฌ์ฉ์ ๋ง์ ๊ฒ ๊ฐ๋ค. ArrayList()์ ์ฝ์
์ ๊ณต๊ฐ์ด ๋ค ์ฐจ์ ์๋ก์ด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ ์๊ฐ์ด ์๋ ํ O(1)
๋ก ๋ฐฐ์ด๊ณผ ๋์ผํ๋ค. (ArrayList๋ ๋ฐฐ์ด๋ก ๊ตฌํํ ๊ฒ์ด๋ผ์ ๋ฐฉ๊ธ ์ค๋ช
ํ ๊ณต๊ฐ์ด ๋ชจ๋ ์ฐจ์ ์๋ก์ด ArrayList ๊ณต๊ฐ์ ์ถ๊ฐํด์ผ ํ๋ ์ํฉ์ด ์๋๋ผ๋ฉด ์กฐํ, ์ญ์ ,์ฝ์
์ ์์ด์ ๋ชจ๋ ์๊ฐ ๋ณต์ก๋๊ฐ ๊ฐ๋ค.) ๊ทธ๋ฌ๋, ArrayList ์ฌ์ฉ์ ๊ทธ๋ ๊ฒ ๊บผ๋ฆด ํ์๋ ์์ ๊ฒ ๊ฐ๋ค.
๊ณต๋ถํ ๋งํฌ : ๋ธ๋ก๊ทธ