[Codeground] 연습문제 - #2. 프로그래밍 경진대회(Java)

[문제 요약]

 - 총 N명의 응시자가 프로그래밍 대회에 참가함

 - 여러 라운드 진행하면서 각 라운드에서 1등은 N 점, 2등은 N-1 점 순으로 순차적으로 점수를 얻게 됨

 - 각 라운드마다 받은 점수의 함이 가장 높은 사람이 최종 우승하게 됨

 - 마지막 라운드 직전까지의 종합 점수가 주어졌을 때, 최종 우승할 가능성 있는 "응시자의 수"를 구하는 프로그램 작성

 - 라운드별로 동점자는 없지만, 종합 점수에서는 동점자가 있을 수가 있으며, 또한 "공동 우승자"가 있을 수 있음

[문제 조건]

 - 제한 시간 : 전체 테스트 케이스는 5개 이하, 전체 수행 시간은 1초 이내(Java 2초 이내)

 - 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB

[입력 조건]

 - 입력 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T ( 1 <= T <= 5 )

 - 각 테스트 케이스의 첫째 줄에는 응시자의 수 N을 나타냄 ( N은 30만 이하의 자연수)

 - 각 테스트 케이스의 두 번째 줄에는 각 응시자가 마지막 라운드 전까지 받은 "종합 점수"를 나타나는 N 개의 정수가 공백(빈칸)을 두고 주어짐

 - 각 숫자는 200만을 넘지 않은 음이 아닌 정수

[출력 조건]

 - 각 테스트 케이스의 답을 순서대로 표준 출력

 - 첫 줄에는 "Case # T"를 출력. 이때 T는 테스트 케이스의 번호

 - 그다음 줄에는 "최종 우승"할 가능성이 있는 응시자의 수를 출력함

---

[정답 문제 풀이]

 - 한 응시자가 최고점을 받은 후의 점수가, 나머지 응시자 중 가장 높은 점수보다 높으면 최종 우승할 수 있다. 가장 높은 점수가 N 점이니깐 한 응시자의 점수에 + N값이다.

 - 나머지 응시자 중 가장 높은 점수를 구해야 한다. 최종 우승하기 위한 조건은 나머지 응시자의 종합 점수가 너무 높으면 안 된다. 그러면 점수가 높은 응시자에게 가장 낮은 점수(1점)를, 낮은 점수를 가진 응시자에게 그다음 높은 점수(N-1 점)를 줘야 가장 적절하다. 부여한 점수 중에 최댓값을 구한 다음에, 한 응시자의 종합 점수 + N 값이 그 최댓값보다 크면 최종 우승할 수 있는 경우가 된다.

 - 배열로 응시자들의 점수들을 입력받은 다음, 오름차순으로 정렬한다. 그리고 가장 낮은 점수부터 높은 점수까지 높은 점수에서 낮은 점수를 더하면서 가장 큰 최댓값을 구한다. 다시 응시자의 점수를 오름차순으로 훑으면서 + N 한 점수가 이전에 구한 최댓값보다 크면 count 하여 최종 우승할 가능성이 있는 응시자의 수를 구한다.

[소스 코드]

/*
You should use the statndard input/output

in order to receive a score properly.

Do not use file input and output

Please be very careful. 
*/
 
import java.util.Arrays;
import java.util.Scanner;
 
/*
   As the name of the class should be Solution , using Solution.java as the filename is recommended.
   In any case, you can execute your program by running 'java Solution' command.
 */
class Solution {
    static int Answer;
 
    public static void main(String args[]) throws Exception {
        /*
         * The method below means that the program will read from input.txt, instead of
         * standard(keyboard) input. To test your program, you may save input data in
         * input.txt file, and call below method to read from the file when using
         * nextInt() method. You may remove the comment symbols(//) in the below
         * statement and use it. But before submission, you must remove the freopen
         * function or rewrite comment symbols(//).
         */
 
        /*
         * Make new scanner from standard input System.in, and read data.
         */
        Scanner sc = new Scanner(System.in);
        // Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int T = sc.nextInt();
        for (int test_case = 0; test_case < T; test_case++) {
 
            Answer = 0;
            /////////////////////////////////////////////////////////////////////////////////////////////
            /*
             * Implement your algorithm here. The answer to the case will be stored in
             * variable Answer.
             */
            int N = sc.nextInt();
            int max = 0, count = 0;
 
            int[] score = new int[N];
 
            for (int i = 0; i < N; i++) {
                score[i] = sc.nextInt();
            }
 
            Arrays.sort(score);
 
            for (int i = 0; i < N; i++) {
                if ((score[i] + N - i) > max)
                    max = score[i] + N - i;
            }
            
            for (int i = 0; i < N; i++) {
                if (score[i] + N >= max) count++;
            }
 
            Answer = count;
            /////////////////////////////////////////////////////////////////////////////////////////////
 
            // Print the answer to standard output(screen).
            System.out.println("Case #" + (test_case + 1));
            System.out.println(Answer);
        }
    }
}

[후기]

 - 2중 for 문을 이용해서 최댓값을 구한 다음에 바로 for 문을 돌려서 응시자의 수를 구하는 소스를 작성했는데 시간 초과로 오답으로 나왔다. for 문을 분리해서 하니깐 시간이 단축되어서 정답으로 처리되었다.