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

링크

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

프로그래머스

 

문제 요약

실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수/스테이지에 도달한 플레이어 수

전체 스테이지 개수, 각 사용자가 현재 멈춰있는 스테이지 번호 stages가 주어질 때 실패율이 높은 스테이지부터 내림차순으로 반환하기

 

제한

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지)까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다.

 

풀이

스테이지 개수는 최대 500, 사용자 수는 최대 200000입니다.

1. stages를 순회하면서 각 스테이지별 도달한 플레이어 수, 도달했으나 아직 클리어하지 못한 플레이어 수를 카운트한다.
   1. 1번 플레이어가 도달한 스테이지가 4라면, 1~4는 도달한 스테이지고 4는 도달했으나 아직 클리어하지 못한 스테이지이다.
2. 순회가 끝난 후, 스테이지별 실패율을 계산한다.
3. 실패율은 기준으로 내림차순으로 정렬한다. 정렬 함수를 재정의하여, 실패율이 같으면 작은 번호의 스테이지가 먼저 오도록 한다.

실패율 기준으로 내림차순으로 정렬하고, 스테이지 번호를 반환해야 하므로 `<스테이지 번호, 실패율>` 형태의 `HashMap`을 떠올릴 수 있습니다.

 

처음에는 실패율이 같은 특수한 경우를 위해 직접 정렬 코드를 직구현해야 되나 고민했습니다.

하지만 `sort`함수를 사용하면 이런 고민조차 하지 않아도 된다는 사실을 깨달았습니다.

(자바 api가 제공하는 기능을 잘 활용할 줄 아는 사람이 되자!)

 

코드

[1차] - 틀린 코드

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] nonClear = new int[N+2];
        for(int i=0; i<stages.length; i++){
            nonClear[stages[i]]++;
        }
        
        HashMap<Integer,Double> fail = new HashMap<>();
        int total = stages.length;
        for(int i=1; i<=N; i++){
            fail.put(i, (double)nonClear[i]/total);
            total -= nonClear[i];
        }
        
        return fail.entrySet().stream().sorted((o1,o2) ->
            Double.compare(o2.getValue(),o1.getValue()))
            .mapToInt(e -> e.getKey()).toArray();
    }
}

• 처음에는 `스테이지에 도달한 사람의 수`과 `스테이지에 도달했으나 아직 클리어하지 못한 사람의 수`를 별도의 배열에 저장했습니다.
• 하지만 배열 한 개만으로도 실패율을 계산할 수 있다는 것을 깨닫고 수정했습니다.
  • 아래 스테이지부터 실패율을 계산하면서, 이전 스테이지에서 클리어하지 못한 사람들을 total에서 빼가면 됩니다.
• 위 코드는 일부 특정 테스트 케이스에서 실패했습니다.
  • 알고 보니, 실패율이 0인 경우에 대해 예외 처리를 하지 않아 발생하는 오류였습니다.
    • `double`은 0/0을 해버리면, 오류가 발생하지 않고 `Nan` 값이 반환됩니다.
    • (제한 사항은 꼭 꼼꼼히 읽도록 하자!)

 

✅ HashMap을 사용한 코드

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] nonClear = new int[N+2];
        for(int i=0; i<stages.length; i++){
            nonClear[stages[i]]++;
        }
        
        HashMap<Integer,Double> fail = new HashMap<>();
        int total = stages.length;
        for(int i=1; i<=N; i++){
            if(total==0){
                fail.put(i,0.0); 
                continue;
            } 
            fail.put(i, (double)nonClear[i]/total);
            total -= nonClear[i];
        }
        
        return fail.entrySet().stream().sorted((o1,o2) ->
            Double.compare(o2.getValue(),o1.getValue()))
            .mapToInt(e -> e.getKey()).toArray();
    }
}

[시간 복잡도]

• M: stages의 길이 = 사용자 수
• N: stage 개수
• 첫 for문: O(M)
• 두 번째 for문: O(N)
• 마지막 sorted() : O(N logN)
• 최종 시간 복잡도 = O(M)+O(N)+O(N log N) = O(M + N log N)

 

🏷 sorted 함수

• `sorted` 함수 내부에 람다 함수를 정의하여, 정렬 기준을 변경했습니다.
• `Double`의 `compare` 함수를 사용하여 `o2.getValue()`와 `o1.getValue()`를 비교했는데, 여기서 매개변수의 순서가 굉장히 중요합니다.
  • sort 함수는 비교 결과가 양수이면, o1과 o2의 순서를 바꿉니다
  • 그리고 `compare`함수는 기본적으로 오름차순으로 정렬합니다. 그리고 compare 함수는 "순서를 바꿔야 할 때" 양수를 반환하는 구조입니다. 
    • o1=3, o2=4라고 해봅시다. compare(o2, o1)=compare(4,3)=1 (오름차순 기준으로 순서를 바꿔야 하므로 1)
    • compare 결과가 양수이므로 sort 함수는 o1과 o2의 순서를 바꿔야 합니다. 그럼 o2, o1 = 4,3 순서로 내림차순이 됩니다.
• `sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()))`
  • 코드의 이 부분을 말로 다시 정의해 봅시다.
    • o2의 값이 o1의 값보다 크다면 `compare`함수는 오름차순 기준에 따라 순서를 바꾸라는 의미에서 양수를 반환하고, `sorted`함수는 비교 결과가 양수이므로 o1과 o2의 순서를 바꾼다.
    • “o2의 값이 o1의 값보다 크다면, o2가 o1보다 앞에 오게 정렬한다(o1과 o2의 순서를 바꾼다)”
    • = 큰 값이 앞에 온다 = 내림차순
• 그럼 `compare` 함수에서 두 값이 같을 때는 어떻게 동작하는 것일까요? 문제 요구사항에 따르면, 두 값이 같을 때는 작은 번호 스테이지 먼저(키 값 기준 오름차순) 동작하도록 해야 합니다.
  • `compare` 함수는 비교하는 두 값이 같으면 0을 반환하게 됩니다. 그리고 `sort` 함수는 0에 대해서는 기존 순서를 유지합니다.
  • 앞서 fail 값들을 계산하여 HashMap에 삽입할 때 스테이지 번호를 하나씩 증가하며 했기 때문에 기존 순서를 유지하면 결국 스테이지 번호 기준 오름차순을 유지하게 됩니다.
  • 따라서, 추가적으로 두 값이 같을 때에 처리하지 않아도 되는 것입니다.

compare 함수 정의

 

---

✅ 다른 방법 - HashMap 대신 Class 정의해서 활용

인덱스와 실패율을 하나로 묶기 위해 이전에는 `HashMap`을 활용했습니다.

하지만 `HashMap`과 `compare` 함수의 문법이 잘 기억나지 않을 수도 있습니다.

 

이럴 때는 별도의 `Class`를 따로 정의해서 정렬 코드를 직접 구현하는 방법도 있습니다.

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] nonClear = new int[N+2];
        for(int i=0; i<stages.length; i++){
            nonClear[stages[i]]++;
        }
        
        ArrayList<Stage>failStages = new ArrayList<>();
        int total = stages.length;
        for(int i=1; i<=N; i++){
            if(total==0){
                failStages.add(new Stage(i,0.0));
                continue;
            } 
            failStages.add(new Stage(i,(double)nonClear[i]/total));
            total -= nonClear[i];
        }
        Collections.sort(failStages);
        return failStages.stream().mapToInt(s -> s.id).toArray();
    }
    
    class Stage implements Comparable<Stage> {
		    public int id;
		    public double fail;
		    
		    public Stage(int id, double fail){
				    this.id = id;
				    this.fail = fail;
		    }
		    
		    @Override
            public int compareTo(Stage s){
                if(fail == s.fail){
                    if(id < s.id) return -1;
                    return 1;
                }
                if(fail>s.fail) return -1;
                return 1;
            }
    }
}

• 정렬 코드를 직접 구현하려면, 내가 정의한 클래스가 `Comparable`인터페이스를 구현해야 합니다.
• 그리고 이 인터페이스를 구현하면 `compareTo`함수를 오버라이드하여 직접 정렬 기준을 정의할 수 있습니다.
  • `compareTo`함수는 나 자신 객체와 매개변수로 전달된 객체를 비교합니다.
  • 마찬가지로 반환값이 1이면 객체의 순서를 바꾼다는 것을 의미합니다.