소프티어 5회 기출 - 성적 평가

난이도 - Lv3

사용 개념 - 구현, 자료구조(PriorityQueue)

풀이 시간 -  50분 ( 설계 10분, 구현 40분 )

핵심 키워드

1. PriorityQueue를 사용함으로써 O(Nlogn) 방식으로 처리 (2차원배열은 O(N²)이라 시간복잡도 안됨)

2. Person 클래스를 생성하여 Score와 Index를 저장할 수 있는 타입을 생성하여 처리.

 

package softeer;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Test5_1 {
    static StringTokenizer st;
    static StringBuilder sb;
    static int n,m,k;
    static class Person implements Comparable<Person>{
        int score, index;
        Person(int score, int index){
            this.score = score;
            this.index = index;
        }
 
        @Override
        public int compareTo(Person o) {
            return Integer.compare(o.score, this.score);
        }
 
        @Override
        public String toString() {
            return "Person{" +
                    "score=" + score +
                    ", index=" + index +
                    '}';
        }
    }
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] result = new int[3][n];
        int[][] arr = new int[3][n];
        sb = new StringBuilder();
        for(int i=0; i<3; i++){
            PriorityQueue<Person> pq = new PriorityQueue<>();
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<n; j++){
                int score = Integer.parseInt(st.nextToken());
                arr[i][j] = score;
                pq.offer(new Person(score,j));
            }
            int grade = 1;
            int cnt = 2;
            Person first = pq.poll();
            int prev = first.score;
            result[i][first.index] = grade;
            boolean flag = false;
            while(!pq.isEmpty()){
                Person now = pq.poll();
                int nowScore = now.score;
                int nowIndex = now.index;
                if(prev == nowScore){
                    flag = true;
                }
                else{
                    flag = false;
                }
                if(flag){
                    result[i][nowIndex] = grade;
                }
                else{
                    result[i][nowIndex] = cnt;
                    grade = cnt;
                }
                cnt++;
                prev = nowScore;
            }
        }
        for(int i=0; i<3; i++){
            for(int j=0; j<n; j++){
                sb.append(result[i][j]+ " ");
            }
            sb.append("\n");
        }
        PriorityQueue<Person> lastPq = new PriorityQueue<>();
        int[] lastResult = new int[n];
        for(int i=0; i<n; i++){
            int sum = 0;
            for(int j=0; j<3; j++){
                sum+=arr[j][i];
            }
            lastPq.offer(new Person(sum, i));
        }
        Person first = lastPq.poll();
        lastResult[first.index] = 1;
        int prev = first.score;
        int cnt=2;
        int grade=1;
        boolean flag = false;
        while(!lastPq.isEmpty()){
            Person now = lastPq.poll();
            int nowScore = now.score;
            int nowIndex = now.index;
            if(prev == nowScore){
                flag = true;
            }
            else{
                flag = false;
            }
            if(flag){
                lastResult[now.index] = grade;
            }
            else{
                lastResult[now.index] = cnt;
                grade = cnt;
            }
            cnt++;
            prev = nowScore;
        }
        for(int i=0; i<n; i++){
            sb.append(lastResult[i]+" ");
        }
        System.out.println(sb.toString().trim());
    }
}
 

 

 

- 마지막에 최종 성적을 구하는 것이 3번의 대회에서 얻은 등수가 기준이 아닌, 점수의 총합으로 이루어지는 것을 늦게 깨닫고 그걸 깨닫는 시간만 20분은 걸린 문제.

- 문제는 5번은 다시 읽어보자