Quartz 4

실패율 (프로그래머스)

5 min read

  • 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
  • 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.
  • 실패율은 다음과 같이 정의한다.
    • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
    • 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
  • https://school.programmers.co.kr/learn/courses/30/lessons/42889

my attempt

import java.util.*;
 
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] challengers = new int[N+2];
        for (int i = 0; i < stages.length; i++) {
            int stage = stages[i];
            challengers[stage] += 1;
        }
        
        Map<Integer, Double> map = new HashMap<>();
        int totalPlayers = stages.length;
        for (int i = 1; i < challengers.length - 1; i++) {
            int failureNum = challengers[i];
            map.put(i, (double) failureNum / totalPlayers);
            totalPlayers -= failureNum;
        }
        
        List<Map.Entry<Integer, Double>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByValue());
        
        System.out.print(list.toString());
        
        return list.stream()
            .mapToInt(Map.Entry::getKey)
            .toArray();
    }
}

THE WRONG

  1. The results are not sorted properly
    • comparingByValue() sorts in ascending order
    • tie breaking is missing
    • fixed:
List<Map.Entry<Integer, Double>> list = new ArrayList<>(map.entrySet());
list.sort((e1, e2) -> {
	int result = Double.compare(e2.getValue(), e1.getValue());
	if (result == 0) {
		return Integer.compare(e1.getKey(), e2.getKey());
	}
	return result;             
});
  1. Edge case: If totalPlayers becomes 0 (because everyone failed at a previous stage), dividing by 0 will give NaN
    • fixed:
Map<Integer, Double> map = new HashMap<>();
int totalPlayers = stages.length;
for (int i = 1; i <= N; i++) {
	int failureNum = challengers[i];
	if (totalPlayers > 0) {
		map.put(i, (double) failureNum / totalPlayers);    
	} else {
		map.put(i, 0.0);
	}
	totalPlayers -= failureNum;
}
  • simplified the for loop to be <= N
  • an example of why this is necessary:
    • stages = [3,3,3,3,3], N = 4
    • challengers = [0, 0, 0, 5, 0, 0]
    • totalPlayers = stages.length = 5
    • in the for loop, when i = 3, then totalPlayers = 0
    • in the next loop, when i = 4, totalPlayers = 0, so when updating our map we put 0.0

solution

import java.util.*;
 
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] challengers = new int[N+2];
        for (int i = 0; i < stages.length; i++) {
            int stage = stages[i];
            challengers[stage] += 1;
        }
        
        Map<Integer, Double> map = new HashMap<>();
        int totalPlayers = stages.length;
        for (int i = 1; i <= N; i++) {
            int failureNum = challengers[i];
            if (totalPlayers > 0) {
                map.put(i, (double) failureNum / totalPlayers);    
            } else {
                map.put(i, 0.0);
            }
            totalPlayers -= failureNum;
        }
        
        List<Map.Entry<Integer, Double>> list = new ArrayList<>(map.entrySet());
        list.sort((e1, e2) -> {
            int result = Double.compare(e2.getValue(), e1.getValue());
            if (result == 0) {
                return Integer.compare(e1.getKey(), e2.getKey());
            }
            return result;             
        });
        
        System.out.print(list.toString());
        
        return list.stream()
            .mapToInt(Map.Entry::getKey)
            .toArray();
    }
}

the book solution

return fails.entrySet().stream()
	.sorted((o1, o2) -> 
		o1.getValue().equals(o2.getValue()) 
		    ? Integer.compare(o1,getKey(), o2.getKey()) // 1
		    : Double.compare(o2.getValue(),o1.getValue())) // 2
	.mapToInt(HashMap.Entry::getKey)
	.toArray();
)
  1. if the value is the same, compare the key (stage)
  2. if they aren’t the same, compare the value (the failure rate, double)

time complexity

  • O(M + NlogN)
    • N = number of stages
    • M = number of players (length of the stages array)
  • It’s actually O(M + N + NlogN)
    • M → iterating to get challengers
    • N→ iterating to put into the map
    • NlogN → sorting the map (after converting to list)
    • we drop the N because we know it’s smaller than NlogN

Graph View

Backlinks