🔗 링크

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

💩 문제

총 스테이지 수 N과 스테이지 현황인 stages가 있다.

스테이지 A의 실패율을 구하는 방법은 아래와 같다.

현재 스테이지가 A인 유저 수 / 현재 스테이지가 A이상인 유저 수

이 때, 실패율이 높은 순으로 구해야한다.

👀 예제로 문제 파악하기

입력 : N 5, stages [2, 1, 2, 6, 2, 4, 3, 3]

• 1번 스테이지 실패율 : 1/8 (1번 스테이지를 지난 사람 8명, 1번 스테이지 클리어중인 사람 1명)
• 2번 스테이지 실패율 : 3/7
• 3번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

따라서 실패율이 높은 순으로 정렬하면 [3,4,2,1,5]이 된다.

😮 알고리즘 풀이 순서

1. Stage 정보를 담을 클래스를 만든다.
   • 고유 번호와 실패율을 가지고 있어야한다.
   • 실패율이 높으면 앞으로 가야하고, 같은 경우에는 고유 번호가 작으면 앞으로 가야한다.
2. List를 선언해준다.
3. 1부터 N+1만큼 반복문을 돈다. (i)
   • stages만큼 반복문을 돈다.
     • i보다 stage가 같거나 크면, clear(현재 스테이지가 A이상인 유저 수)을 1 누적해준다.
     • i와 stage가 같으면, now(현재 스테이지가 A인 유저 수)를 1 누적해준다.
   • list에 고유 번호와 실패율(now/clear)을 넣어 만들어진 Stage 객체를 추가해준다.
     • 0으로 나누는 일을 방지하기 위해, if문을 추가해서clear가 0이면 무조건 실패율을 0으로 해서 리스트에 추가해준다.
4. list를 정렬해준다.
5. list를 배열로 바꾸어서 리턴해준다.

👨‍💻 코드

public class Solution {
  public int[] solution(int N, int[] stages) {

    List<Stage> list = new ArrayList<>();

    for (int i = 1; i < N + 1; i++) {
      int now = 0;
      int clear = 0;

      for (int stage : stages) {
        if (i <= stage) {
          clear += 1;
        }
        if (i == stage) {
          now += 1;
        }
      }

      if (clear == 0) {
        list.add(new Stage(i, 0));
      } else {
        list.add(new Stage(i, (double) now / clear));
      }
    }

    list.sort(Stage::compareTo);
    return list.stream().mapToInt(Stage::getNum).toArray();
  }

  @Test
  public void 정답() {
    Assert.assertArrayEquals(new int[]{3, 4, 2, 1, 5}, solution(5, new int[]{2, 1, 2, 6, 2, 4, 3, 3}));
    Assert.assertArrayEquals(new int[]{4, 1, 2, 3}, solution(4, new int[]{4, 4, 4, 4, 4}));
    Assert.assertArrayEquals(new int[]{7, 6, 5, 4, 3, 2, 1, 8}, solution(8, new int[]{1, 2, 3, 4, 5, 6, 7}));
  }

}

class Stage implements Comparable<Stage> {

  private int num; // 고유번호
  private double failure; // 실패율

  public int getNum() {
    return num;
  }

  public Stage(int num, double failure) {
    this.num = num;
    this.failure = failure;
  }

  @Override
  public int compareTo(Stage o) {
    if (this.failure == o.failure) {
      return this.num < o.num ? -1 : 1;
    } else {
      return this.failure > o.failure ? -1 : 1;
    }
  }
}