๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algorithm

[Algorithm/JAVA][ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์‹คํŒจ์œจ

๋ฐ˜์‘ํ˜•

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์‹คํŒจ์œจ

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์— ๋„ฃ์–ด์ค€๋‹ค.

๋ฐฐ์šด์ 

  1. Map์„ Value๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์ •๋ง ๋‹ค์–‘ํ•˜๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. ๋งŽ์€ ๋ฐฉ๋ฒ•์ค‘์— ์ œ์ผ ๋‚ด๊ฐ€ ์‰ฝ๋‹ค๊ณ ? ๋งˆ์Œ์—๋“œ๋Š”? ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜์˜€๋‹ค. fail์˜ key๊ฐ’์„ ๊ฐ€์ง€๊ณ ์žˆ๋Š” keySet์ด๋ผ๋Š” List๋ฅผ ๋งŒ๋“ค์–ด์ฃผ์–ด์„œ ์ด keySet์„ sortํ•ด์ฃผ๋Š”๋ฐ ๋น„๊ตํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ง์ ‘ ๋„ฃ์–ด์ฃผ์—ˆ๋‹ค.
    keySet.sort((o1,o2) -> fail.get(o2).compareTo(fail.get(o1)));
    ์œ„ ๋ฐฉ์‹์€ keySet์—์„œ ํ•˜๋‚˜์”ฉ ๊ฐ€์ ธ์™€์„œ fail์—์„œ get(key)๋ฅผ ์ด์šฉํ•ด์„œ Value๊ฐ’์„ ๋น„๊ตํ•˜์—ฌ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์ค€๋‹ค.
    ์ด๋•Œ o2์™€ o1์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟ”์ฃผ๋ฉด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ์ด ๋œ๋‹ค.
  2. 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;
        }
    }
}
๋ฐ˜์‘ํ˜•