[pg] 프로그래머스 실패율

1. 문제 정의

 각 스테이지별로 도전자가 있고, 패스한 인원이 있다.

 

실패율은 스테이지 도전인원 / (스테이지 도전인원+패스한 인원)

 

현재 유저들이 도전하고 있는 스테이지의 번호가 담긴 배열이 주어질 때 각 스테이지 별 실패율을 구해서, 실패율이 높은 순으로 스테이지 번호를 리턴.

 

2. 내가 시도한 방법.

 스테이지 번호, 실패율, 그리고 실패율을 구하기 위한 도전인원과 패스인원을 구하는 게 핵심이기 때문에 Stage라는 객체를 만들어서 스테이지 번호와 실패율을 하나로 관리하였고, 도전인원의 count를 관리하기 위해서 처음에는 map을 선언, 나중에는 배열 이용해서 count를 관리하였다. 전체인원 관리는 전체인원을 선언한 후에 하위 스테이지의 실패율을 구할 때마다 빼주면서 구현하였다.

 이 문제를 처음 풀었을 때는 <스테이지 번호, 각 스테이지별 도전하고 있는 인원 count> 를 map으로 만들어서 스테이지 당 도전하고 있는 도전자 수를 그때마다 맵에서 검색해서 찾아 쓰는 형식으로 구현했는데, 속도가 느린 것 같아 배열을 이용하여 count를 계산했더니 속도가 훨씬 빨라졌다.

3. code

풀이 1

public class Solution {

    public int[] solution(int N, int[] stages) {
        /*
         * 스테이지 번호와 실패율을 가지고 있는 스테이지들을 저장할 List
         */
        List<Stage> answer = new ArrayList<>();

        /*
         * 스테이지 별로 몇 명이 도전하고 있는지를 카운트해서 저장할 map
         */
        Map<Integer, Integer> map = new HashMap<>();

        /*
         * 실패율을 구하기 위해서는 인원수가 필요하기 때문에 정의.
         */
        double userCount = stages.length;

        /*
         * 스테이지 별로 몇 명 도전하는지 카운트 하는 로직
         */
        for (int stageNumber : stages) {
            if (!map.containsKey(stageNumber)) {
                map.put(stageNumber, 1);
            } else {
                map.put(stageNumber, map.get(stageNumber) + 1);
            }
        }

        /*
         * 스테이지 별 유저 카운트를 가지고 있는 맵을 이용해서 실패율을 계산하여 리스트에 스테이지 객체를 저장.
         */
        for (int stage = 1; stage <= N; stage++) {
            Integer challengingPersonCount = map.getOrDefault(stage,0); // 해당 스테이지 카운트
            Double failRate = challengingPersonCount / userCount; // 실패율 계산
            answer.add(new Stage(stage, failRate)); // 리스트에 스테이지 객체 추가
            userCount -= challengingPersonCount; // 하위 스테이지 인원 제거
        }

        /*
         * 스테이지 객체를 가지고 있는 리스트를 실패율에 따라 sort
         */
        Collections.sort(answer, (o1, o2) -> {
            if (o1.getFailRate() < o2.getFailRate()) {
                return 1;
            }
            else if (o1.getFailRate() > o2.getFailRate()) {
                return -1;
            }
            else {
                if (o1.getStageNumber() < o2.getStageNumber()) {
                    return -1;
                }
                else {
                    return 1;
                }
            }
        });

        /*
         * 정렬된 리스트를 배열로 변환하여 리턴
         */
        return answer.stream().map(stage -> stage.getStageNumber()).mapToInt(i -> i).toArray();
    }

    /**
     * 스테이지 번호와 실패율을 가지고 있는 스테이지 객체
     */
    static class Stage {
        int stageNumber;
        double failRate;

        public Stage(int stageNumber, double failRate) {
            this.stageNumber = stageNumber;
            this.failRate = failRate;
        }

        public int getStageNumber() {
            return stageNumber;
        }

        public double getFailRate() {
            return failRate;
        }
    }


}

 

 풀이2

public class Solution2 {

    public int[] solution(int N, int[] stages) {
        /*
         * 스테이지 객체를 가지고 있는 리스트
         */
        List<Stage> answer =new ArrayList<>();

        /*
         * 스테이지 별 카운트 정보를 가지고 있는 배열
         */
        int[] countArray = new int [N+2];

        /*
         * 실패율을 구하기 위해선 전체인원이 필요하기 때문에 선언
         */
        double userCount = stages.length;

        /*
         * 스테이지 별 인원을 카운팅
         */
        for (int stage : stages) {
            countArray[stage] +=1;
        }

        /*
         * 스테이별로 순회하면서 실패율 계산 및 스테이지 객체를 리스트에 저장.
         */
        for (int stage = 1 ; stage <= N; stage++){
            Integer presentChallengingPersonCount = countArray[stage]; // 현재 도전하는 사람들의 수
            Double failRate = presentChallengingPersonCount / userCount; // 실패율 계산
            answer.add(new Stage(stage, failRate)); // 스테이지정보와 실패율을 가지고 있는 스테이지 객체를 리스트에 저장
            userCount -= presentChallengingPersonCount; // 하위 스테이지 인원 제거
        }

        /*
         * 실패율을 비교하면서 sort
         */
        Collections.sort(answer, (o1, o2) -> {
            if(o1.getFailRate() < o2.getFailRate()) return 1;
            else if (o1.getFailRate() > o2.getFailRate()) return -1;
            else{
                if (o1.getStageNumber()<o2.getStageNumber()) return -1;
                return 1;
            }
        });

        /*
         * sort된 stage객체를 stage번호로 매핑하고, array로 만들어서 리턴.
         */
        return answer.stream().map(stage -> stage.getStageNumber()).mapToInt(i->i).toArray();
    }

    /**
     * 스테이지 번호와 실패율을 가지고 있는 스테이지 객체
     */
    static class Stage {
        int stageNumber;
        double failRate;

        public Stage(int stageNumber, double failRate) {
            this.stageNumber = stageNumber;
            this.failRate = failRate;
        }

        public int getStageNumber() {
            return stageNumber;
        }

        public double getFailRate() {
            return failRate;
        }
    }
}

 

4. 깨달은 점

 배열의 랜덤액세스와 map의 해시를 통한 인덱스 접근은 시간복잡도로는 O(1)로 같지만, 실제로 체감해보니 map의 key 보다는 배열의 index를 이용한 접근이 훨씬 속도가 빨랐다.

 

참조

https://school.programmers.co.kr/learn/courses/30/lessons/42889