[프로그래머스] 실패율 (KAKAO BLIND RECRUITMENT) (JAVA)

https://school.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 으로 정의한다.

---

※ JAVA 코드 (실패율)

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public static int[] solution(int N, int[] stages) {

        // 인원수
        int len = stages.length;
        int user_count = len; // 전체 인원수
        float failRt = 0;
        int user_acc = 0;

        // 각 스테이지의 실패율을 담을 맵
        Map<Integer, Float> failure = new LinkedHashMap<Integer, Float>();

        // int 배열을 int형 리스트로 담는다
        List<Integer> lst = Arrays.stream(stages).boxed().collect(Collectors.toList());

        // 스테이지 1 ~ N까지에서 해당 스테이지에 머무르고 있는 인원의 수를 미리 담는다
        for(int i = 1; i <= N; i++){
            // 해당 값의 개수를 세어
            int user_cnt = Collections.frequency(lst, i);
            user_acc += user_cnt; // 스테이지별 유저 수 누적

            if(user_cnt == 0){
                failRt = 0;
            } else {
                failRt = (float) user_cnt / (float) user_count;
            }
            
            // 전체 유저수에서 누적된 유저를 제외한다
            user_count = len - user_acc;
            failure.put(i, failRt);
        }
        // 실패율 맵의 키셋(스테이지)을 담는다
        List<Integer> keySet = new ArrayList<>(failure.keySet());
        
        // Value기준으로 Map sort
        keySet.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return failure.get(o2).compareTo(failure.get(o1));
            }
        });
        int idx = 0;
        int[] answer = new int[N];

        for(Integer key : keySet){
            answer[idx++] = key;
        }

        return answer;
    }
}

---

※ 생각정리 (실패율)

오늘은 프로그래머스에 있는 2019 카카오 블라인드 테스트 문제를 풀어본다.

이 문제는 카카오가 참 알고리즘 문제를 잘 만든다는 것을 느낄 수 있게 해주었다. 이전에도 몇번의 카카오 문제를 풀어볼때마다 항상 느끼는 것은 해당 문제들은 우리가 알고리즘적으로 또는 자바 문법적으로 다양한 생각을 할 수 있게 도와준다는 것이다.

먼저 stages 배열이 파라미터로 주어진다. 배열의 각원소는 해당 지점에서 각 게임이용자가 머물고 있는 stage를 나타낸다. 즉 stage[0] = 유저1이 머무르고 있는 스테이지, stage[1] = 유저2가 머무르고 있는 스테이지이다.

우리는 각 스테이지마다 머물고 있는 인원 수를 구해야하며, 몇가지 방법으로 해당 스테이지의 인원수를 구할 수 있다.

1. 반복문으로 개수세기  : 가장 쉽게 생각해볼 수 있는 방법이다. stages배열의 끝까지 돌며 각 해당 원소배열의 수를 올린다. 코드로 만들어 본다면 다음과 같다.

int [] arr = new int[N]; // N은 스테이지의 개수
Arrays.fill(arr, 0); 	 // 각 원소를 0으로 초기화
for(int i = 0 ; i < stages.length; i++){
    arr[stages[i]]++;    // 해당 스테이지가 오면 개수증가
}

 

2. Collections.frequency() : Java.util.Collections의 frequency()를 활용하면 각 배열의 원하는 값의 개수를 쉽게 구할 수 있다. (숫자, 문자 모두 가능)

// 스테이지 1 ~ N까지
for(int i = 1; i <= N; i++){
    // 해당 값의 개수를 세어 user_cnt에 담는다
    int user_cnt = Collections.frequency(lst, i);
}

 

상황에 따라서 활용할 수 있는데 해당 개수를 배열에 담아 계속해서 사용하고자 한다면 첫번째 방법을 단순히 개수만 구하고 이후 로직에 쓰지 않는다면 두번째 방법을 사용할 수 있겠다.

 

각 스테이지별 실패율을 구하고 Map<Integer(스테이지), Float(실패율)>() 맵에 해당 결과를 담았다. 키값을 스테이지로 하고 실패율을 Value담아두었다.

이제 해당 실패율을 내림차순 정렬해야한다. 여기서는 KeySet()을 활용했다.

// 실패율 맵의 키셋(스테이지)을 담는다
List<Integer> keySet = new ArrayList<>(failure.keySet());

// Value기준으로 Map 내림차순 정렬
keySet.sort(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return failure.get(o2).compareTo(failure.get(o1));
    }
});

 

문제에서는 실패율이 같을 경우에는 스테이지가 낮은 값이 우선순위에 와야한다는 내용이 있지만 이미 스테이지별로 정렬되어있기 때문에 해당 부분은 생략한다.

// answer 배열에 최종 스테이지값을 담는다
int[] answer = new int[N];

for(Integer key : keySet){
    answer[idx++] = key;
}

 

 

-새벽코딩-