실패율

문제 풀러가기

문제 설명

failrate

  슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

  이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

  • 실패율은 다음과 같이 정의한다.
    • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

  전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

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

입출력 예

N stages result
5 [2, 1, 2, 6, 2, 4, 3, 3] [3, 4, 2, 1, 5]
4 [4, 4, 4, 4, 4] [4, 1, 2, 3]

입출력 예 설명

입출력 예 #1

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번스테이지의 실패율은 다음과 같다.

  • 1번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

  • 2번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

  • 3번 스테이지 실패율 : 2/4
  • 4번 스테이지 실패율 : 1/2
  • 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

  • [3, 4, 1, 2, 5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

  • [4, 1, 2, 3]

코드

class Solution {
  static class fail {
    int num;
    double rate;

    fail(int num, double rate) {
      this.num = num;
      this.rate = rate;
    }
  }

  public int[] solution(int N, int[] stages) {
    int[] now = new int[N + 1];

    for(int i = 0; i < stages.length; i++) {
      if(stages[i] != N + 1) {
        now[stages[i]]++;
      }
    }

    int total = stages.length;
    fail[] fails = new fail[N + 1];
    fails[0] = new fail(1000, -1);

    for(int i = 1; i < now.length; i++) {
      if(total == 0) {
        fails[i] = new fail(i, 0);
      } else {
        fails[i] = new fail(i, (double)now[i] / total);
      }
      total -= now[i];
    }

    Arrays.sort(fails, new Comparator<fail>() {
      public int compare(fail o1, fail o2) {
        if(o1.rate != o2.rate) {
          return -Double.compare(o1.rate, o2.rate);
        }
        return o1.num - o2.num;
      }
    });

    int[] answer = new int[N];

    for(int i = 0; i < N; i++) {
      answer[i] = fails[i].num;
    }

    return answer;
  }
}

설명

  이 문제는 실패율을 구해서 정렬해야 하는 문제이다.

  각 스테이지에 멈춰있는 사용자의 수를 구하기 위한 코드를 작성한다. stages에 주어진 숫자들은 각 유저의 현재 위치를 나타낸 것이다. 따라서 현재 위치를 저장할 배열을 만들고 입력된 숫자의 개수를 카운트해 스테이지 별 사용자 수를 구한다.

public int[] solution(int N, int[] stages) {
  int[] now = new int[N + 1];

  for(int i = 0; i < stages.length; i++) {
    if(stages[i] != N + 1) {
      now[stages[i]]++;
    }
  }

stages의 길이는 전체 사용자 수와 동일하다. 따라서 전체 사용자수 total을 stages의 길이와 같다고 한다. 첫 번째 스테이지부터 순차적으로 검사하여 실패율을 구하고 매 스테이지를 지날 때마다 이전 스테이지에 머무는 사용자의 수를 빼면서 계산한다.

  int total = stages.length;
  fail[] fails = new fail[N + 1];
  fails[0] = new fail(1000, -1);

  for(int i = 1; i < now.length; i++) {
    if(total == 0) {
      fails[i] = new fail(i, 0);
    } else {
      fails[i] = new fail(i, (double)now[i] / total);
    }
    total -= now[i];
  }

각 스테이지 별 실패율을 구했으니 정렬을 해야할 차례이다. int형 인자와 double형 인자를 동시에 처리해야하므로 Comparator를 사용하여 처리하였다. 실패율이 같은 경우 작은 번호를 출력하도록 만들고 정렬된 값을 배열 answer에 저장한 후 출력하면 된다.

    Arrays.sort(fails, new Comparator<fail>() {
      public int compare(fail o1, fail o2) {
        if(o1.rate != o2.rate) {
          return -Double.compare(o1.rate, o2.rate);
        }
        return o1.num - o2.num;
      }
    });

    int[] answer = new int[N];

    for(int i = 0; i < N; i++) {
      answer[i] = fails[i].num;
    }

    return answer;
  }
}

중간에 사용된 fail은 스테이지의 번호와 그 스테이지의 실패율을 하나로 묶기 위해서 따로 생성한 클래스이다.

  static class fail {
    int num;
    double rate;

    fail(int num, double rate) {
      this.num = num;
      this.rate = rate;
    }
  }