[프로그래머스 Level 1] 실패율

문제

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

프로그래머스

 

 

풀이

• 게임의 스테이지 별로 실패율을 구해, 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담긴 배열을 구해야 한다.
• 실패율이란, '스테이지에 도달한 플레이어 수'에서 '스테이지를 클리어하지 못한 플레이어 수'를 나눈 값이다.
• 전체 스테이지 개수 N과 현재 사용자들이 멈춰있는 스테이지의 번호가 담긴 배열 stages가 주어진다.
• stages의 1번 인덱스에는 1번 사용자가 멈춰있는 스테이지 번호가 담겨있고 이 배열의 길이는 1 이상 200,000 이하이다.
• 스테이지 개수 N은 1 이상 500 이하이다.
• stages에는 1 이상 N + 1 이하의 값이 담겨있다. N + 1은 모든 스테이지를 클리어 한 사람을 말한다.
• 실패율이 같다면 작은 번호가 먼저 오도록 한다.
• 스테이지에 멈춘 유저가 없는 경우 실패율은 0으로 한다.

 

문제의 조건이 길기 때문에 차근차근 읽을 필요가 있다. 요점은 각 스테이지의 실패율을 구하고, 이를 내림차순으로 정렬할 방법을 찾는 것이다.

 

실패율을 구하기 전에, 각 스테이지에 머무는 사람의 수를 알 필요가 있다. 정수형 1차원 배열 stageCount를 선언한다.

이때, 모든 스테이지를 클리어한 N+1과, 1번부터 시작하는 스테이지 번호를 모두 고려해 N+2의 크기로 초기화한다.

n번 인덱스는 n번 스테이지에 머무는 사람을 의미한다.

int[] stageCount = new int[N + 2];

for (int i = 0; i < stages.length; i++) {
    stageCount[stages[i]]++;
}

 

실패율을 기준으로 스테이지 번호를 출력하기 위해서는 두 값 모두 필요하다. 그렇기 때문에 스테이지 번호를 Key, 실패율을 Value로 가지는 HashMap<Integer, Double> map을 선언한다.실패율을 구하기 위해선 스테이지에 도달한 사람의 수를 구해야 한다. 스테이지에 도달한 사람의 수는 곧 전체 사용자 수에서 이 전 스테이지들에 머무는 사람들의 수를 뺀 값이다. 전체 사용자 수는 stages 배열의 길이가 된다.

HashMap<Integer, Double> map = new HashMap<>();
double total = stages.length;

 

각 스테이지별 실패율을 구하는 반복문을 만든다. 이때, 실패율이 0이 되는 경우는 스테이지에 머무는 사람이 없다는 뜻으로,  stageCount[i]의 값이 0인 경우이다. 한 스테이지의 실패율은 stageCount[i] / total이 된다.

total은 다음 스테이지로 넘어갈 때, 현재 스테이지에 머문 사용자 수인 stageCount[i]만큼 줄어들어야 한다.

for (int i = 1; i <= N; i++) {
    if (stageCount[i] == 0) {
        map.put(i, 0.0);
        continue;
    }

    map.put(i, stageCount[i] / total);
    total -= stageCount[i];
}

 

반복문이 끝나면 HashMap에는 각 스테이지별 실패율이 담겨 있다. 실패율을 기준으로 스테이지 번호를 내림차순 정렬하기 위해서는 Key와 Value 둘 다 접근해야 하기 때문에, entrySet()을 사용한다. getValue()를 사용해 Value에 접근하고, Double.compare()을 사용해 각 값을 비교한다.

List<HashMap.Entry<Integer, Double>> entryList = new ArrayList<>(map.entrySet());
Collections.sort(entryList, (o1, o2) -> Double.compare(o2.getValue(), o1.getValue()));

 

정렬된 List를 순서대로 정수형 배열에 담아 출력하면 문제가 해결된다.

 

전체 코드 (Java)

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
		int[] stageCount = new int[N + 2];

		for (int i = 0; i < stages.length; i++) {
			stageCount[stages[i]]++;
		}

		HashMap<Integer, Double> map = new HashMap<>();
		double total = stages.length;

		for (int i = 1; i <= N; i++) {
			if (stageCount[i] == 0) {
				map.put(i, 0.0);
				continue;
			}

			map.put(i, stageCount[i] / total);
			total -= stageCount[i];
		}

		List<HashMap.Entry<Integer, Double>> entryList = new ArrayList<>(map.entrySet());
		Collections.sort(entryList, (o1, o2) -> Double.compare(o2.getValue(), o1.getValue()));
		
		int answer[] = new int[entryList.size()];
		for (int i = 0; i < entryList.size(); i++) {
			answer[i] = entryList.get(i).getKey();
		}
        
        return answer;
        
        /*
        return map.entrySet().stream()
            .sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()))
			.mapToInt(HashMap.Entry::getKey).toArray();
        */
    }
}

 

후기

실패율을 유도하는 방법은 쉽게 떠올랐지만, HashMap과 EntrySet으로 문제를 해결하는데 시간을 많이 잡아먹었다.

또한 Stream API를 이용해 map을 정렬하고 배열로 바꾸는 방법이 존재하는데, 아직 코딩테스트에 사용할 정도로 익숙하지 않은 것 같다. 강력한 API인 만큼 빠르게 습득하도록 해야겠다.