[코딩테스트연습] 실패율

LaStella·2021년 10월 28일
0

- 문제

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

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

제한사항

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

- 전체코드

import java.util.*;

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

        int[] stagesCount = new int[N+1]; //N+1은 마지막 스테이지까지 클리어  한 사용자
        Fail[] failRate = new Fail[N]; //스테이지 번호와 실패율이 담길 객체

        //멈춰있는 스테이지 각 갯수를 저장
        for(int i : stages) {
            stagesCount[i-1]++;
        }
        
        //스테이지는 1번부터시작이나 i는 0번부터시작것에 주의
        for(int i = 0 ; i < N ; i++) {
            int stagesSum = 0;
            //i번째 스테이지의 실패율은 i/(i부터 N번째에 도달한 사람의 수)이다. 여기서 N번째는 모든 스테이지를 클리어한 사람이다.
            for(int j = i ; j < stagesCount.length ; j++) {
                stagesSum += stagesCount[j];
            }
            //스테이지에 도달한 유저가 없을 경우
            if(stagesSum == 0) {
                failRate[i] = new Fail(i, 0);    
            }
            else {
                failRate[i] = new Fail(i, (double) stagesCount[i]/stagesSum);    
            }
        }
        
        Arrays.sort(failRate);
        
        for(int i = 0 ; i < N ; i++) {
            answer[i] = failRate[i].stageNum+1;
        }

        return answer;
    }
}
class Fail implements Comparable<Fail> {
    int stageNum;
    double failRate;

    public Fail(int stageNum, double failRate) {
        this.stageNum = stageNum;
        this.failRate = failRate;
    }

    public int compareTo(Fail fail) {
        //실패율은 내림차순
        if(this.failRate < fail.failRate) {
            return 1;
        }
        //실패율이 같으면 스테이지 번호 오름차순(작은 번호의 스테이지가 먼저)
        else if(this.failRate == fail.failRate) {
            if(this.stageNum > fail.stageNum) {
                return 1;
            }
        }
        return -1;
    } 
}

- 막혔던 점 & 해결방법

처음 문제를 풀 때 실패율을 저장할 공간으로 2차원 배열을 생각하였다. 스테이지는 N까지 있으므로 N행 2열을 가지는 2차원 배열을 만들어 1열에는 스테이지의 번호를, 2열에는 스테이지의 실패율을 저장하여 이를 2열의 값에 따라 정렬하여 1열의 값들을 answer로 return 하는 방법이었다. 하지만 실패율은 소수이므로 자료형으로 double을 사용하여야 하므로 double타입의 2차원배열을 사용하게 되면 answer로 내보낼 값들에 int형으로 캐스팅해야 했다. 또 다른 문제로는 배열의 정렬기준이 두 개(실패율 내림차순, 스테이지번호 오름차순)이므로 이를 적절하게 바꿔주기 위해서는 compare메소드를 오버라이드하여 수정해야 했다.[참고글] 이런 부분을 Solution 내에서 하기에는 코드가 직관적이지 못하여 가독성을 떨어뜨린다고 생각하여 Fail이라는 객체를 만들어 직관적인 코드로 바꾸었다. [참고글]

- 느낀점

이번 문제를 푸는데 가장 껄끄러웠던 부분은 스테이지의 번호는 1부터 시작하지만, 이를 저장하는 자료형들의 인덱스는 0부터 시작하므로 1번 스테이지 = 0번 스테이지 라고 생각하면서 푸는 것이 너무 헷갈렸다. 이 부분은 객체를 만들어 풀면서 다소 해소되었지만, 처음에는 2차원 배열을 사용하여 풀려고 하였기에 스테이지의 번호와 배열의 인덱스를 머릿속에서 생각하면서 잦은 혼동이 왔다. 좀 더 익숙해지면 해결될 문제라고 생각한다.

profile
개발자가 되어가는 중...

0개의 댓글