[ํ๋ก๊ทธ๋๋จธ์ค] ์คํจ์จ
https://programmers.co.kr/learn/courses/30/lessons/42889
๋ฌธ์ ์ค๋ช
์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋
๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์คํ
์ด์ง ์ฐจ์ด๊ฐ ๋๋ฌด ํฐ ๊ฒ์ด ๋ฌธ์ ์๋ค.
์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํ ๊น ๊ณ ๋ฏผ ํ ๊ทธ๋ ๋ ๋์ ์ผ๋ก ๊ฒ์ ์๊ฐ์ ๋๋ ค์ ๋์ด๋๋ฅผ ์กฐ์ ํ๊ธฐ๋ก ํ๋ค. ์ญ์ ์ํผ ๊ฐ๋ฐ์๋ผ ๋๋ถ๋ถ์ ๋ก์ง์ ์ฝ๊ฒ ๊ตฌํํ์ง๋ง, ์คํจ์จ์ ๊ตฌํ๋ ๋ถ๋ถ์์ ์๊ธฐ์ ๋น ์ง๊ณ ๋ง์๋ค. ์ค๋ ๋ฆฌ๋ฅผ ์ํด ์คํจ์จ์ ๊ตฌํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ผ.
์คํจ์จ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค.
์คํ
์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ
์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์ ์ฒด ์คํ
์ด์ง์ ๊ฐ์ N, ๊ฒ์์ ์ด์ฉํ๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด stages๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์คํจ์จ์ด ๋์ ์คํ
์ด์ง๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ฒจ์๋ ๋ฐฐ์ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ๋ผ.
์ ํ์ฌํญ
- ์คํ ์ด์ง์ ๊ฐ์ N์ 1 ์ด์ 500 ์ดํ์ ์์ฐ์์ด๋ค.
- stages์ ๊ธธ์ด๋ 1 ์ด์ 200,000 ์ดํ์ด๋ค.
- stages์๋ 1 ์ด์ N + 1 ์ดํ์ ์์ฐ์๊ฐ ๋ด๊ฒจ์๋ค.
- ๊ฐ ์์ฐ์๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋์ ์ค์ธ ์คํ ์ด์ง์ ๋ฒํธ๋ฅผ ๋ํ๋ธ๋ค.
- ๋จ, N + 1 ์ ๋ง์ง๋ง ์คํ ์ด์ง(N ๋ฒ์งธ ์คํ ์ด์ง) ๊น์ง ํด๋ฆฌ์ด ํ ์ฌ์ฉ์๋ฅผ ๋ํ๋ธ๋ค.
- ๋ง์ฝ ์คํจ์จ์ด ๊ฐ์ ์คํ ์ด์ง๊ฐ ์๋ค๋ฉด ์์ ๋ฒํธ์ ์คํ ์ด์ง๊ฐ ๋จผ์ ์ค๋๋ก ํ๋ฉด ๋๋ค.
- ์คํ ์ด์ง์ ๋๋ฌํ ์ ์ ๊ฐ ์๋ ๊ฒฝ์ฐ ํด๋น ์คํ ์ด์ง์ ์คํจ์จ์ 0 ์ผ๋ก ์ ์ํ๋ค.
Code
Java
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
double[] cnt = new double[N];
double num = (double)stages.length;
Map<Integer, Double> fail = new HashMap<>();
for(int i=0; i<stages.length; i++){
if(stages[i]==N+1) continue;
cnt[stages[i]-1]++;
}
for(int i=0; i<cnt.length; i++){
if(num==0){
fail.put(i, 0.0);
continue;
}
fail.put(i, cnt[i]/num);
num -= cnt[i];
}
List<Integer> keySet = new ArrayList<Integer>(fail.keySet());
keySet.sort((o1,o2) -> fail.get(o2).compareTo(fail.get(o1)));
int i = 0;
for(Integer key : keySet){
answer[i++] = key+1;
}
return answer;
}
}
Code ์ค๋ช
cnt์ stage๋ณ๋ก ์ธ์์๋ฅผ ๋ฃ์ด์ฃผ๊ณ ๋ชจ๋ ๋ค ํด๋ฆฌ์ดํ ์ฌ๋์ continue๋ฅผ ์ฌ์ฉํด ๋๊ฒจ์ค๋ค.
๊ทธ๋ฆฌ๊ณ fail์ด๋ผ๋ Map์ ์คํ
์ด์ง(key)์ ์คํจ์จ(value)์ ๊ณ์ฐํ์ฌ ๋ฃ์ด์ฃผ๊ณ
fail์ ์คํจ์จ(value)๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ answer์ ๋ฃ์ด์ค๋ค.
๋ฐฐ์ด์
- Map์ Value๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ ๋ฐฉ๋ฒ์ด ์ ๋ง ๋ค์ํ๋ค๋ ๊ฒ์ ์๊ฒ ๋์๋ค. ๋ง์ ๋ฐฉ๋ฒ์ค์ ์ ์ผ ๋ด๊ฐ ์ฝ๋ค๊ณ ? ๋ง์์๋๋? ๋ฐฉ๋ฒ์ ์ฌ์ฉํ์๋ค. fail์ key๊ฐ์ ๊ฐ์ง๊ณ ์๋ keySet์ด๋ผ๋ List๋ฅผ ๋ง๋ค์ด์ฃผ์ด์ ์ด keySet์ sortํด์ฃผ๋๋ฐ ๋น๊ตํ๋ ํจ์๋ฅผ ์ง์ ๋ฃ์ด์ฃผ์๋ค.
์ ๋ฐฉ์์ keySet์์ ํ๋์ฉ ๊ฐ์ ธ์์ fail์์ get(key)๋ฅผ ์ด์ฉํด์ Value๊ฐ์ ๋น๊ตํ์ฌ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ค๋ค.keySet.sort((o1,o2) -> fail.get(o2).compareTo(fail.get(o1)));
์ด๋ o2์ o1์ ์์น๋ฅผ ๋ฐ๊ฟ์ฃผ๋ฉด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ์ด ๋๋ค. - Class๋ฅผ ์ด์ฉํด์ ํธ๋ ๋ฐฉ์
๋ค๋ฅธ์ฌ๋์ ํ์ด์ค์ ๊ฐ์ฅ ์ข์์๋ฅผ ๋ง์ด ๋ฐ์ ํ์ด์ด๋ค. Stage๋ผ๋ ํด๋์ค๋ฅผ ๋ฐ๋ก ์ ์ธํด์ฃผ์ด์ ์ฌ์ฉํ๊ณ compareToํจ์๋ฅผ ๋ฃ์ด์ค์ ๊ฐ๋ ์ฑ์ด ์ข์ ํจ์์ธ๊ฒ ๊ฐ๋ค.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public int[] solution(int N, int[] lastStages) {
int nPlayers = lastStages.length;
int[] nStagePlayers = new int[N + 2];
for (int stage : lastStages) {
nStagePlayers[stage] += 1;
}
int remainingPlayers = nPlayers;
List<Stage> stages = new ArrayList<>();
for (int id = 1 ; id <= N; id++) {
double failure = (double) nStagePlayers[id] / remainingPlayers;
remainingPlayers -= nStagePlayers[id];
Stage s = new Stage(id, failure);
stages.add(s);
}
Collections.sort(stages, Collections.reverseOrder());
int[] answer = new int[N];
for (int i = 0; i < N; i++) {
answer[i] = stages.get(i).id;
}
return answer;
}
class Stage implements Comparable<Stage> {
public int id;
public double failure;
public Stage(int id_, double failure_) {
id = id_;
failure = failure_;
}
@Override
public int compareTo(Stage o) {
if (failure < o.failure ) {
return -1;
}
if (failure > o.failure ) {
return 1;
}
return 0;
}
}
}
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm/Java][ํ๋ก๊ทธ๋๋จธ์ค] [1์ฐจ] ๋น๋ฐ์ง๋ (0) | 2021.10.02 |
---|---|
[Algorithm/Java][ํ๋ก๊ทธ๋๋จธ์ค] 3์ง๋ฒ ๋ค์ง๊ธฐ (0) | 2021.09.05 |
[Algorithm/Java][ํ๋ก๊ทธ๋๋จธ์ค] ์ง์ ๊ตฐ ์ถ์ฒํ๊ธฐ (0) | 2021.08.27 |
[Algoritm/Java][ํ๋ก๊ทธ๋๋จธ์ค] ์ ๊ท ์์ด๋ ์ถ์ฒ (0) | 2021.07.28 |
[Algorithm/Java][ํ๋ก๊ทธ๋๋จธ์ค] ๋คํธ ๊ฒ์ (0) | 2021.07.23 |