[Sorfteer] 인증평가(5차) 기출 - 성적 평가 (Java)

문제

현주는 N명의 인원이 참여하는 프로그래밍 스터디 그룹을 이끌고 있다.

현주는 스터디를 위해 대회를 세 개 개최하였고, 모든 구성원이 각 대회에 참여하였다. 참가자는 각 대회에서 0 이상 1,000 이하의 정수인 점수를 얻는다. 한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있을 수 있다.

현주는 각 대회별 등수 및 최종 등수를 매기고 싶다. 등수는 가장 점수가 높은 사람부터 1등, 2등, ···, N등의 순서대로 붙는다. 만일 동점이 있을 경우 가능한 높은 (등수의 수가 작은) 등수를 부여한다. 즉, 점수가 내림차순으로 10,7,6,6,4의 순서일 경우, 6점을 받은 두 사람은 공동 3등이 되고, 그 다음 순서인 4점을 받은 사람은 5등이 된다. 이 규칙을 다르게 표현하면 다음과 같다: 각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다. 대회별 등수는 각 대회에서 얻은 점수를 기준으로 하며 최종 등수는 세 대회의 점수의 합을 기준으로 한다.

각 참가자의 대회별 등수 및 최종 등수를 출력하는 프로그램을 작성하시오.

 

 

제약조건

3 ≤ N ≤ 100,000

 

 

 

입력 형식

첫째 줄에 참가자의 수를 나타내는 정수 N이 주어진다.
이어 세 개의 줄에 각 대회의 결과를 나타내는 N개의 정수가 주어진다. 이중 i번째 정수는 그 대회에서 i번째 사람이 얻은 점수를 의미한다.

 

 

출력 형식

첫 세 개의 줄에는 각 참가자의 대회별 등수를 출력한다. 즉 이중 c번째 줄의 i번째 정수는 c번째 대회에서의 i번째 사람의 등수를 의미한다.
이어 새로운 줄에 같은 형식으로 각 참가자의 최종 등수를 출력한다.

 

 

나의 소스코드

import java.util.*;
import java.io.*;


public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());

        List<Pair> temp;

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

        for (int i = 0; i < N; i++) {
            result.add(new Pair(i, 0));
        }

        for (int i = 0; i < 3; i++) {
            String[] arr = reader.readLine().split(" ");

            temp = new ArrayList<>();

            for (int j = 0; j < N; j++) {
                int score = Integer.parseInt(arr[j]);
                temp.add(new Pair(j, score));
                result.get(j).score += score;
            }

            List<Pair> copyList = new ArrayList<>(temp);
            Collections.sort(copyList);

            for (int j = 0; j < N; j++) {
                if (j == 0) {
                    copyList.get(j).rank = 1;
                    continue;
                }
                
                if (copyList.get(j).score == copyList.get(j - 1).score) {
                    copyList.get(j).rank = copyList.get(j - 1).rank;
                } else {
                    copyList.get(j).rank = j + 1;
                }
            }

            for (Pair p : temp) {
                System.out.print(p.rank + " ");
            }

            System.out.println();
        }

        temp = new ArrayList<>(result);
        Collections.sort(temp);

        for (int i = 0; i < N; i++) {
            if (i == 0) {
                temp.get(i).rank = 1;
                continue;
            }

            if (temp.get(i).score == temp.get(i - 1).score) {
                temp.get(i).rank = temp.get(i - 1).rank;
            } else {
                temp.get(i).rank = i + 1;
            }
        }

        for (Pair p : result) {
            System.out.print(p.rank + " ");
        }

    }
}

class Pair implements Comparable<Pair> {
    int index;
    int score;
    int rank;

    public Pair(int index, int score) {
        this.index = index;
        this.score = score;
        rank = 0;
    }

    @Override
    public int compareTo(Pair p) {
        return p.score - this.score;
    }
}

 

 

피드백

문제를 보면 그렇게 어렵게 느껴지는 알고리즘의 문제가 아니다. 처음 작성한 코드는 다음과 같다. 

import java.util.*;
import java.io.*;


public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());

        List<Integer> finalRank = new ArrayList<Integer>();
        
        for (int i = 0; i < 3; i++) {
            finalRank.add(0);
        }
        
        for (int i = 0; i < 3; i++) {
            List<Integer> tempList = new ArrayList<>();
            String[] inputData = reader.readLine().split(" ");

            for (int j = 0; j < N; j++) {
                int tempValue = Integer.parseInt(inputData[j]);
                tempList.add(tempValue);
                finalRank.set(j, finalRank.get(j) + tempValue);
            }

            printRank(tempList);
        }

        printRank(finalRank);
    }

    public static void printRank(List<Integer> data) {
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < data.size(); i++) {
            int target = data.get(i);
            int rank = 1;
            for (int j = 0; j < data.size(); j++) {
                if (target < data.get(j)) {
                    rank++;
                }
            }
            result.append(rank).append(i != data.size() ? " " : "");
        }

        System.out.println(result);
    }
}

정말 단순하게 모든 요소에 대한 반복문을 돌면서 rank는 1로 초기화하고, 자신 보다 큰 점수가 있을 때 마다 1씩 증가시켜서 최종 rank를 자신의 등수에 넣는 형식의 코드입니다.

 

하지만 문제를 제출하고 보니 오답인 부분은 하나도 없었지만 8개정도가 시간 초과가 나왔다. 그 말은 즉... 위 로직에서 나올 수 있는 최대 시간 복잡도인 N * N이 나오면 안 된다는 뜻이다.

 

처음 작성했던 로직으로 풀고 싶어서 별 짓을 다해봤다. Map을 사용해서 점수에 대한 등수를 갱신하면서 같은 점수가 나오면 바로 get()을 통해서 가져올 수도 있게도 해봤다. 하지만 이 경우에도 10만개의 점수 데이터가 모두 다르다면 최대 100000 * 100000의 시간 복잡도가 나오기 때문에 별로 의미없는 코드였다.

 

그렇게 계속 고민을 하다가 소프티어 문제 해설에 적혀있는 내용을 봤다. 각 대회의 점수를 저장할 배열 temp[]를 선언하고, Pair<번호, 점수>의 객체를 사용하라는 내용이었다. 그래서 번호와 점수를 속성값으로 가지고 있는 Pair라는 클래스를 만들었고, 점수를 기준으로 내림차순할 수 있도록 만들었다. 내림차순으로 정렬한 후 첫 번째 Pair 객체는 무조건 rank가 1이다. 그 뒤 부터는 이전 Pair 객체의 점수와 비교해서 같으면 이전 Pair 객체의 등수를 넣고, 다르면 본인의 index에 해당하는 값을 넣어주면 된다.

 

이렇게 풀이를 하고 제출하니...정답이 나왔다...오늘도 잠 못 잘 뻔했다.

 

레벨 3문제는...정말 이전에도 그렇고 머리가 아프다.