등수 구하기. 자바

알고리즘 문제를 풀다보면 한번씩 나오는 문제가 있는데요.

 

바로 주어진 입력 내에서 a가 몇 등인지 구하는 문제

 

 

보통 풀이 방법으로

입력값의 개수를 n이라고 했을 때

a라는 사람 한명의 등수를 구하는 문제라고 하면, 

 

입력값 n을 한번씩만 탐색하면 되므로 시간 복잡도는 O(n)이 됩니다.

 

그런데 n명 모두의 등수를 구하라고 하면 시간 복잡도는 n * n 해서 O(n^2)이 됩니다.

 

 

실전 알고리즘에서 시간복잡도가 O(n^2) 인 경우는 좋지 못한 알고리즘이라고 부릅니다. 

그래서 조금 개선해보고자 이 글을 작성합니다.

 

 

문제

 

n 명의 학생의 점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성합니다.
같은 점수가 입력될 경우 동일한 등수로 처리하고, 높은 등수로 처리한다.

예를 들어서 20점 20점 100점 10점이 존재하면 각각 2등, 2등, 1등, 4등이 되는 것이다.

 

 

입력

 

첫 줄에 N(3<=n<=100)이 입력되고, 두 번째 줄에 점수를 의미하는 n개의 정수가 입력 됩니다.

 

입력예제

 

6

77 79 82 100 66 77

 

출력예제

 

4 3 2 1 6 4

 

 

 

 

시간복잡도가 O(n^2) 인 풀이

 

// 앞에서 부터 하나하나 세는 방법
public static String solution(int[] arr) {
    int total = arr.length;
    int[] result = new int[total];

    for (int i=0; i<total; i++) {

        int rank = 1;

        for (int j=0; j<total; j++) {

            // 같은 대상이면
            if (i == j) {
                continue;
            }

            int myScore = arr[i];
            int otherScore = arr[j];

            // 나보다 다른 사람의 점수가 높으면 등수 ++
            if (otherScore > myScore) {
                rank++;
            }
        }

        result[i] = rank;
    }

    return Arrays.toString(result);
}

public static void main(String[] args) {
    int[] input = {77,79,82,100,66,77};

    System.out.println(solution(input));
}

 

결과

 

[4, 3, 2, 1, 6, 4] 

 

출력 결과는 얼마든 조절할 수 있기 때문에 일단 위와 같이 바로 보이도록 출력하였습니다. 참고 부탁드립니다.

 

 

 

 

시간 복잡도가 O(n)인 풀이

 

각각의 점수를 매기려고 하면 for문을 중첩해야 하므로 시간복잡도가 O(n^2)이지만, 점수별로 몇등에 해당하는지를 구하면 시간 복잡도는 O(101 * n) => 정확하게 표기하면 O(n) 이 된다.

왜냐면, 점수는 0점부터 100점까지 101개 밖에 없기 때문에 해당 점수보다 높은 사람이 몇명 있는지만 구하면 되기 때문이다. 

이 때 101은 상수이기 때문에 시간복잡도 표기법에서 사라지게 되고 결론적으로 O(n)이 된다. 

 

이것은 입력값의 크기가 커지면 커질 수록 조금 더 효율적인 로직이 되나, 입력값이 101보다 작을 때는 그다지 효율적이지 않다.

 

 

public class Test {

    // 점수에 해당하는 등수
    private static int[] rankOfScore = new int[101];

    private static int[] input = {77,79,82,100,66,77};

    static {

        // 점수를 기준으로 점수보다 더 낮은 사람이 있는지 확인
        for (int score = 0; score <= 100; score++) {

            int rank = 1;
            // 사람 수만큼 반복
            for (int i=0; i<input.length; i++) {

                // 오직 이 점수보다 높은 점수에 몇명이 있는지만 판별
                if (input[i] > score) {
                    rank++;
                }
            }

            rankOfScore[score] = rank;
        }

    }
    
    // 미리 구해놓은 등수표를 가지고 구하는 방법
    public static String solution(int[] scores) {

        List<Integer> result = new ArrayList<>();

        for (int score : scores) {
            result.add(rankOfScore[score]);
        }

        return Arrays.toString(result.toArray());
    }
    

    public static void main(String[] args) {
        System.out.println(solution(input));
    }
    
}

 

 

결과

 

[4, 3, 2, 1, 6, 4]