-
[Algo Rhythm๐บ๐] 2019 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๋ฆฌํฌ๋ฃจํ ์คํจ์จAlgo Rhythm๐บ๐/others 2020. 7. 4. 22:44
๋ฌธ์ ์ค๋ช
์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋ ๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์คํ ์ด์ง ์ฐจ์ด๊ฐ ๋๋ฌด ํฐ ๊ฒ์ด ๋ฌธ์ ์๋ค.
์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํ ๊น ๊ณ ๋ฏผ ํ ๊ทธ๋ ๋ ๋์ ์ผ๋ก ๊ฒ์ ์๊ฐ์ ๋๋ ค์ ๋์ด๋๋ฅผ ์กฐ์ ํ๊ธฐ๋ก ํ๋ค. ์ญ์ ์ํผ ๊ฐ๋ฐ์๋ผ ๋๋ถ๋ถ์ ๋ก์ง์ ์ฝ๊ฒ ๊ตฌํํ์ง๋ง, ์คํจ์จ์ ๊ตฌํ๋ ๋ถ๋ถ์์ ์๊ธฐ์ ๋น ์ง๊ณ ๋ง์๋ค. ์ค๋ ๋ฆฌ๋ฅผ ์ํด ์คํจ์จ์ ๊ตฌํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ผ.
-
์คํจ์จ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค.
-
์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
-
์ ์ฒด ์คํ ์ด์ง์ ๊ฐ์ N, ๊ฒ์์ ์ด์ฉํ๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ ์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด stages๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์คํจ์จ์ด ๋์ ์คํ ์ด์ง๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์คํ ์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ฒจ์๋ ๋ฐฐ์ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ๋ผ.
์ ํ์ฌํญ
-
์คํ ์ด์ง์ ๊ฐ์ N์ 1 ์ด์ 500 ์ดํ์ ์์ฐ์์ด๋ค.
-
stages์ ๊ธธ์ด๋ 1 ์ด์ 200,000 ์ดํ์ด๋ค.
-
stages์๋ 1 ์ด์ N + 1 ์ดํ์ ์์ฐ์๊ฐ ๋ด๊ฒจ์๋ค.
-
๊ฐ ์์ฐ์๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋์ ์ค์ธ ์คํ ์ด์ง์ ๋ฒํธ๋ฅผ ๋ํ๋ธ๋ค.
-
๋จ, N + 1 ์ ๋ง์ง๋ง ์คํ ์ด์ง(N ๋ฒ์งธ ์คํ ์ด์ง) ๊น์ง ํด๋ฆฌ์ด ํ ์ฌ์ฉ์๋ฅผ ๋ํ๋ธ๋ค.
-
๋ง์ฝ ์คํจ์จ์ด ๊ฐ์ ์คํ ์ด์ง๊ฐ ์๋ค๋ฉด ์์ ๋ฒํธ์ ์คํ ์ด์ง๊ฐ ๋จผ์ ์ค๋๋ก ํ๋ฉด ๋๋ค.
-
์คํ ์ด์ง์ ๋๋ฌํ ์ ์ ๊ฐ ์๋ ๊ฒฝ์ฐ ํด๋น ์คํ ์ด์ง์ ์คํจ์จ์ 0 ์ผ๋ก ์ ์ํ๋ค.
์ด๋ป๊ฒ ํ์๋
import java.util.ArrayList; import java.util.Comparator; class FailureOfStage { public int stage; public double failure; public FailureOfStage(int stage, double failure) { this.stage = stage; this.failure = failure; } public int getStage() { return stage; } public double getFailure() { return failure; } } class Solution { public int[] solution(int N, int[] stages) { int[] answer; int numTotalPlayer = stages.length; int[] numStageClearPlayer = new int[N + 1]; ArrayList<FailureOfStage> failureOfStages = new ArrayList<>(); int numChallenger = 0; for(int challengingStage : stages) { numStageClearPlayer[challengingStage - 1]++; } for(int i = 0; i < N; i++) { int stage = i + 1; double failure = (numTotalPlayer == numChallenger) ? 0 : (double) numStageClearPlayer[i] / (numTotalPlayer - numChallenger); failureOfStages.add(new FailureOfStage(stage, failure)); numChallenger += numStageClearPlayer[i]; } failureOfStages.sort(Comparator.comparing(FailureOfStage::getFailure).reversed().thenComparing(FailureOfStage::getStage)); answer = failureOfStages.stream().mapToInt(FailureOfStage::getStage).toArray(); return answer; } }
์ ์ ๋ ๊ฒ ํ์๋
๋งค๊ฐ๋ณ์๋ก stage์ ๊ฐ์๋ฅผ ์๋ฏธํ๋ N๊ณผ ํ๋ ์ด์ด๊ฐ ๋์ ์ค์ธ stage์ธ 1์ฐจ์ ๋ฐฐ์ด stages ์ฃผ์ด์ง๋ค. ์ด๋ stages์์ N + 1์ด ์ฃผ์ด์ง๋ฉด N๋ฒ์งธ ์คํ ์ด์ง๊น์ง ๋ชจ๋ ํด๋ฆฌ์ดํ๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค.
์ฒ์ฒํ ์๊ฐํด๋ณด๋ n๋ฒ์งธ ์คํ ์ด์ง๋ฅผ ๋์ ์ค์ด๋ผ๋ ๋ง์ n-1๋ฒ์งธ ์คํ ์ด์ง๊น์ง๋ ํด๋ฆฌ์ดํ๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค๋ ๊ฒ์ ์ ์ ์๋ค.
(n๋ฒ์งธ ์คํ ์ด์ง ๋์ ์ค) = (n-1๋ฒ์งธ ์คํ ์ด์ง๊น์ง๋ ํด๋ฆฌ์ด)
๊ทธ๋์ ๊ฐ ์คํ ์ด์ง๋ณ ํด๋ฆฌ์ดํ ์ฌ๋์ ์๋ฅผ ์๋ฏธํ๋ ํฌ๊ธฐ๊ฐ N + 1์ธ ๋ฐฐ์ด์ ๋ง๋ ๋ค stages๋ฅผ traverseํ์ฌ ์ด๋ฅผ ํ์ ํ๋ค. ๊ด๋ จ ์ฝ๋๋ ์๋์ ๊ฐ๋ค.
... int[] numStageClearPlayer = new int[N + 1]; … for(int challengingStage : stages) { numStageClearPlayer[challengingStage - 1]++; }
๋ค์์ผ๋ก ๊ฐ ์คํ ์ด์ง๋ณ ์คํจ์จ์ ๊ตฌํ๋๋ฐ ์คํจ์จ์ ์ ์๋ ์๋์ ๊ฐ๋ค.
์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์ด๋ฅผ ๋ ์ ํํ๊ฒ ์์ฑํ๋ฉด ์๋์ ๊ฐ๋ค.
i๋ฒ์งธ ์คํ ์ด์ง๋ฅผ ๋์ ์ค์ธ ํ๋ ์ด์ด์ ์ / i๋ฒ์งธ ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์ด๋ฅผ ์กฐ๊ธ ๋ ์๊ฐํ๋ฉด ์๋์ ๊ฐ์ด ๋ฐ๊ฟ ์ ์๋ค๋ ๊ฒ์ ์ ์ ์๋ค.
(i-1)๋ฒ์งธ ์คํ ์ด์ง๋ฅผ ํด๋ฆฌ์ดํ ์ฌ๋์ ์ / (์ ์ฒด ํ๋ ์ด์ด ์ - (i - 1) ๋ฒ์งธ ์คํ ์ด์ง๋ฅผ ๋์ ์ค์ธ ์ฌ๋์ ์)
๋ฌธ์ ์์ ์ํ๋ ๊ฒ์ ์คํจ์จ์ด ๋ฎ์ ์์๋ก ์คํ ์ด์ง๋ฅผ ์ ์ฅํ๊ณ ์คํจ์จ์ด ๊ฐ์ ๊ฒฝ์ฐ ์คํ ์ด์ง๊ฐ ๋์ ์์๋ก ์ ์ฅํ๋ ๊ฒ์ธ๋ฐ ์ด๋ฅผ ์ํด ์คํจ์จ๊ณผ ์คํ ์ด์ง ๋ฒํธ๋ฅผ ์ ์ฅํ๋ FailureOfStage๋ผ๋ ํด๋์ค๋ฅผ ์ ์ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์คํจ์จ์ ๊ณ์ฐํ ๋ค FailureOfStage๋ฅผ ์ ์ฅํ๋ ArrayList์ ์ ์ฅํ๋ค. ๊ด๋ จ ์ฝ๋๋ ์๋์ ๊ฐ๋ค.
int numTotalPlayer = stages.length; ArrayList<FailureOfStage> failureOfStages = new ArrayList<>(); int numChallenger = 0; … for(int i = 0; i < N; i++) { int stage = i + 1; double failure = (numTotalPlayer == numChallenger) ? 0 : (double) numStageClearPlayer[i] / (numTotalPlayer - numChallenger); failureOfStages.add(new FailureOfStage(stage, failure)); numChallenger += numStageClearPlayer[i]; }
๊ทธ ๋ค๋ก๋ ๊ฐ๋จํ๋ค. ์คํจ์จ ๊ธฐ์ค์ผ๋ก ๋ด๋ฆผ์ฐจ์, ์คํจ์จ์ด ๊ฐ์ผ๋ฉด ์คํ ์ด์ง๋ฅผ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๋ค arraylist์์ stage๋ฅผ ๋ฝ์ ๋ค์ array์ ์ ์ฅํ๋ฉด ๋๋ค. ๊ด๋ จ ์ฝ๋๋ ์๋์ ๊ฐ๋ค.
failureOfStages.sort(Comparator.comparing(FailureOfStage::getFailure).reversed().thenComparing(FailureOfStage::getStage)); answer = failureOfStages.stream().mapToInt(FailureOfStage::getStage).toArray();
๋ฌด์์ ๋ฐฐ์ ๋
์ด ๋ฌธ์ ๋ ์ง๋ฌธ์ ์ดํดํ๋๋ฐ ์๊ฐ์ด ์๋นํ ์ค๋ ๊ฑธ๋ ธ๋ ๋ฌธ์ ์๋ค. ํ์ง๋ง ์ฒ์ฒํ ์๊ฐํด๋ณด๋ ๋ฌธ์ ์ ์๋๋ฅผ ํ์ ํ ์ ์์๋ค. ์ด๋ฅผ ํตํด ์ฒ์ฒํ ๊ทธ๋ฆฌ๊ณ ๊น๊ฒ ์๊ฐํ๋ ๊ฒฝํ์ ํ ์ ์์๋ค.
๋ํ Comparator๋ผ๋ class์์ static method๋ก ์ ๊ณตํ๋ comparing๊ณผ thenComparing์ ์ฒ์ ์ฌ์ฉํด๋ดค๋๋ฐ ๊ธฐ์กด์ ๋๋ค์์ผ๋ก compare๋ฅผ ์ ์ํ๋ ๊ฒ๋ณด๋ค ์ฝ๊ณ ํธ๋ฆฌํ๋ค. ์์ผ๋ก ์์ฃผ ์ฌ์ฉํด์ผ๊ฒ ๋ค.
'Algo Rhythm๐บ๐ > others' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
-