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

Programmers - [42889] 실패율

---

🖍 게임의 각 스테이지의 실패율을 구하여 내림차순으로 스테이지 정렬 후 출력하는 문제
(link) 42889 (2019 KAKAO BLIND RECRUITMENT) 실패율 (Lv.1)

---

[풀이 과정]

다른 포스팅보다 스크롤이 조금 더 길다. 🥺

카카오 코테 답게 문제 이해가 쉬운 편은 아니다. 물론 카오코테 1번 문제 수준으로 그다지 어려운 문제는 아니지만, 2년 전의 나는 못 풀었고 조금 도움을 받아 코드제출만 했었다. 그래서 지금 포스팅하는 시점에서 다시 이해하고 풀이를 적고 있다.

 

문제에서 정의하고 있는 개념을 먼저 설명해보겠음.

우선 입력값에 대해서 말해보자면

N = 스테이지 개수이며, 입력으로 주어지는 stage 배열은 [index = 플레이어 번호, value = 멈춰있는 스테이지 번호] 이다.

만약 모두 클리어한 플레이어라면 stage[index] 값에 N+1, 즉 스테이지 개수의 +1값이 들어오게 된다.

이때 stage.length = 플레이어 전체 인원 수 가 된다.

 

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

문제에서 제시한 실패율의 정의이다. 천천히 읽으면 무슨 말인지 알 수 있다.

이는 간단하게 말하자면 [실패율 = 멈춘 인원 / 도달 인원] 이다.

플레이어를 중심으로 이해하지 말고, 스테이지를 중심으로 봐야 한다.

사용할 변수들과 함께 설명하도록 하겠다.

 

다음은 문제 풀이에 사용될 배열이다.

멈춘 인원 (stop[i]) : 스테이지 i 에서 멈춘(=실패한) 인원 수를 저장한다.
도달 인원 (reach[i) : 스테이지 i 에 도달한 적 있는 인원 수를 저장한다.
이때 각 배열의 인덱스는 스테이지 번호가 된다.

(배열의 인덱스는 0부터 쓸 것이므로 본래는 스테이지의 값에서 1을 뺀 수를 인덱스로 사용해야 하지만 용이한 설명을 위해 스테이지 번호를 그대로 적겠음)

만약에 스테이지 5에서 실패하고 멈춰있는 사람이 한 명 있다고 가정해보자.

그렇다면 stop[5]의 값이 +1 증가할 것이다.

또한, 스테이지 5에서 멈췄다면 스테이지 1 ~ 4는 클리어하고, 스테이지 5에 도달해있는 상태이다.

따라서 reach[1] ~ reach[4]의 값은 물론 reach[5]의 값 까지 +1 증가하여 갱신되는 것이다.

 

이때, 모두 클리어한 플레이어의 경우 멈춘 스테이지 값이 N+1이므로 stop 배열의 크기는 N+1로 정의한다.

---<첨언>---

이건 지금 포스팅하다가 떠오른 건데, 굳이 N+1의 크기로 선언하지 않아도 풀 수 있는 방법은 있다.

stage의 값이 N+1인 경우, stop 배열 갱신은 건너뛰고 바로 reach 배열을 갱신하는 방법을 사용할 수 있을 것 같다.

현재 코드를 보면 stop 배열의 마지막 인덱스는 전혀 사용하지 않고 있다.

스테이지는 N까지 있으므로 answer 배열에 반환될 스테이지 번호도 N까지이다. 그러므로 쓸 데 없이 N+1 인덱스 까지 만들어둘 필요는 없을 것 같다.

----------------

stop 배열과 reach 배열은 for문으로 stage배열 값에 접근하여 채울 수 있다.

 

 

 

여기까지가 실패율을 구하기 위한 요소들이다. 이제 각 스테이지 별 실패율을 저장해야 한다.

이를 저장하기 위해 실패율 클래스를 따로 정의하였다. (이하 FailureRate)

FailureRate 클래스는 변수로 (1) 스테이지 번호(=stage)와, (2) 해당 스테이지의 실패율(=fail)을 가진다.

stop과 reach 배열이 모두 채워졌다면 실패율은 다음과 같이 구할 수 있다.

FailureRate.fail = stop[idx]/reach[idx]

(물론 필자는 웬만하면 클래스 변수에 접근할 때 getter, setter를 사용한다. 이해의 편의를 위해 위와 같이 작성하였음)

 

스테이지 하나마다 FailureRate 객체를 하나씩 생성하여 스테이지 번호와 실패율을 저장한다.

만들어진 객체는 ArrayList에 저장할 것이다. 모두 저장이 되면 리스트 내부의 객체들을 정렬해야 한다.

리스트 자체는 객체에 정렬 메소드인 sort()를 가지고 있다. 따라서 sort() 메소드에 매개변수로 Comparator 내부 메소드를 넣어주어 오름차순 또는 내림차순으로 정렬이 가능하지만, 지금은 조금 다른 방법을 사용해야 한다.

 

우선 우리는 정렬을 위한 기준을 잡아주어야 한다.

첫 번째 기준은 실패율, 즉 클래스 변수 fail이다.

만약 실패율이 동일할 경우, 두 번째 기준은 스테이지 번호인 stage이다.

 

정렬 기준이 정수 한 개와 같은 단일 기준이라면 좋겠지만, 매우 아쉽게도 그렇지 않기 때문에 우리는 Comparator의 메소드를 반드시... 재정의(@Override)하여 사용해야 한다. Comparator는 객체를 비교하기 위한 인터페이스이다. 따라서 compare(T o1, T o2) 메소드를 구현해주어야 사용이 가능하다. 정렬을 하기 위해서 리스트에 들어 있는 요소 두 개를 선정하여 객체의 내부 변수를 비교해야 하므로 compare 메소드의 매개변수는 FailureRate 객체 1과, FailureRate 객체 2가 되겠다.

 

아무튼 각각의 객체 두 개를 가지고 비교를 해야 하므로 compare 메소드를 정의해줄 것이며, Comparator는 한 번 사용될 것이기 때문에 따로 클래스로 빼줄 필요 없이 익명 클래스로 작성할 것이다. (물론 클래스를 따로 빼도 상관은 없다)

글이 너무 길어질 것 같아 compare 메소드를 정의하는 방법은 더보기란에 빼두겠음

compare(T o1, T o2)의 기본적인 동작 방식을 설명하자면,

(o1.변수를 선행 원소, o2.변수를 후행 원소라고 했을 때)

(선행 원소 > 후행 원소) 이면 1을 반환한다.

(선행 원소 = 후행 원소) 이면 0을 반환한다.

(선행 원소 < 후행 원소) 이면 -1을 반환한다.

이때 굳이 -1, 0, 1일 필요는 없다. 그냥 음수, 0, 양수이면 되나, 1을 반환하는 게 보기 좋다.

따라서 여기서 알 수 있는 것은, 반환값 = 선행 원소 - 후행 원소 라는 점이다.

조건문으로 달아주는게 직관적이고 이해가 쉽지만, 간단하게 정리하여 바디 없이 다음과 같이 쓸 수도 있다.

> return o1.argument - o2.argument

1이 반환되면 선행원소가 더 크므로 뒤쪽으로 배치될 것이다. -1이 반환된다면 그 반대로 동작한다.

오름차순 정렬은 이런 식으로 진행된다

다만 우리는 정렬 조건이 두 개이므로, 0이 반환되는 경우의 바디 부분에 두 번째 정렬 조건을 가지고 또 써줘야한다.

 

대충 설명했으니 한 번 짜보자

근데 주의할 점이 있다. 반환값 = 선행 - 후행 이라고 위에 적어두었는데, 또 불행하게도 우리의 첫 번째 정렬 조건은 정수가 아니라 실수다. 그러므로 첫 번째 정렬 조건 만큼은 일일이 조건문을 달아 반환값을 -1, 0, 1 로 적어주자.

 

완성된 코드를 먼저 보겠다.

list.sort(new Comparator<failureRate>() {
    @Override
    public int compare(failureRate f1, failureRate f2) {
        if(f1.getFail() > f2.getFail())
            return -1;
        else if(f1.getFail() < f2.getFail())
            return 1;
        else
            return f1.getStage() - f2.getStage();
    }

});

 

fail 변수를 비교하는 부분을 먼저 살펴본다.

분명 위에서 선행 원소 > 후행 원소 이면 1을 반환한다고 했던 것 같다. 그런데 왜 -1을 반환했나?

우리는 실패율을 오름차순이 아닌 내림차순으로 정렬해야 하기 때문이다. 즉, 선행 원소가 더 크다면 앞쪽에 배치해야 한다. 때문에 오름차순으로 정렬할 때와 반대로 반환한다.

 

그 다음, fail 변수가 같을 경우 else문이 실행되면서 stage 변수를 비교하게 된다.

stage 변수는 정수이므로, 위에서 간단하게 만들었던 코드를 사용할 수 있다.

stage의 경우 더 빠른 번호를 앞으로 배치해야 하므로, 반대로 써줄 필요 없이 "선행 원소 - 후행 원소"를 반환한다.

(아래 코드 전문은 옛날에 작성했던 그대로 가져왔기 때문에 조건문이 전부 적혀있다)

--------------------

리스트를 정렬했다면 이제 정답을 저장할 배열에 순서대로 넣어주기만 하면 된다.

answer 배열은 프로그래머스 자체에 이미 선언이 되어있을 것이다.

리스트에 들어있는 객체에서 스테이지 번호에 접근하여 순서대로 하나하나씩 배열에 넣고 그대로 반환해주면 끝.

 

---

[Pseudocode]

// (1) 스테이지 n에 멈춰있는 인원 갱신
1. for i : 0 ~ stage.length
	2. int n = stage[i]
	3. stop[n-1]++

// (2) 스테이지 n을 통과한(또는 도달한) 인원 갱신
	4. for j : 0 ~ n
    	5. if (j == N) break;
		6. reach[j]++
        
// (3) <failure> 타입의 리스트에 실패율 계산하여 입력
	7. for j : 0 ~ N
    	8. list.add(new FailureRate(j+1, stop[j]/reach[j]))
        
// (4) 실패율 내림차순 정렬
	9. list.sort // Comparator 사용
    
// (5) answer 배열에 리스트의 요소들을 순서대로 저장
10. for i : 0 ~ N
11. answer[i] = list.get(i).getStage()

---

[Code]

import java.util.*;

/**
 * 프로그래머스 42889번
 * 실패율
 * 
 */
public class Problem14 {
    public static void main(String[] args) {
        int N = 5;
        int[] stages = {2, 1, 2, 6, 2, 4, 3, 3};
        System.out.println(Arrays.toString(solution(N, stages)));
    }

    public static int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        int[] reach = new int[N]; // 도달 인원
        int[] stop = new int[N+1]; // 멈춘 인원
        ArrayList<failureRate> failure = new ArrayList<>(); // 실패율 저장 (실패율 + 스테이지)

        for(int i=0 ; i<stages.length ; i++) { // 인원 수 만큼 반복
            int n = stages[i];
            stop[n-1]++; // 멈춘 인원 측정
            for (int j=0; j<n; j++) { // 도달 인원 카운트
                if(j == N)
                    break;
                reach[j]++;
            }
        }

        for (int j=0; j<N; j++) { // 리스트에 스테이지 별 실패율 입력
            failure.add(new FailureRate(j+1, (float)stop[j]/reach[j]));
        }

        failure.sort(new Comparator<FailureRate>() { // 실패율 내림차순 정렬
            @Override
            public int compare(FailureRate f1, FailureRate f2) {
                if(f1.getFail() > f2.getFail())
                    return -1;
                else if(f1.getFail() < f2.getFail())
                    return 1;
                else {
                    if(f1.getStage() < f2.getStage())
                        return -1;
                    else if(f1.getStage() > f2.getStage())
                        return 1;
                    return 0;
                }
            }
        });

        for (int i=0 ; i<N ; i++) {
            answer[i] = failure.get(i).getStage();
        }

        return answer;
    }
}

class FailureRate {
    private int stage;
    private float fail; 

    public FailureRate(int stage, float fail) {
        this.setStage(stage);
        this.setFail(fail);
    }

    public int getStage() {
        return stage;
    }
    public void setStage(int n) {
        this.stage = n;
    }
    public float getFail() {
        return fail;
    }
    public void setFail(float f) {
        this.fail = f;
    }
}

---

[Result]

---

(2021.08.01 풀이분)

포스팅하는데 꽤 오래걸렸다.

중간중간 딴 짓도 좀 하긴 했지만, 푼 지 1년도 더 넘은 문제라서 기억이 잘 안나는 바람에 아예 문제 이해부터 다시 시작했다. 내게 남아있는건 작성된 코드 밖에 없었다.... 그래서 의사코드도 다시 썼다.

그리고 아직 Comparator 인터페이스의 개념이 내 머리 속에서 정리가 제대로 안 된 상태였어서, 포스팅 하는 김에 조금 찾아봤다. 풀 당시에는 그냥 무지성으로 따라 썼을 것이다.

 

긴 글 읽느라 정말 수고해주신 여러분께 박수 💜