[CodeGround] Practice - 프로그래밍 경진대회

문제

삼성 프로그래밍 경진대회는 권위 있는 대회이다. 대회는 여러 라운드를 통해서 진행되며, 모든 라운드에 총 N명의 응시자가 있다.
각 라운드 별로 1등은 N점, 2등은 N−1점 순으로 순차적으로 점수를 얻게 되고 뒤에서 2등은 2점, 뒤에서 1등은 1점을 얻게 된다.
그리고 각 라운드 별로 동점자는 없으며, 각 라운드 마다 받은 점수의 합이 제일 높은 사람이 우승하게 된다. 
마지막 라운드 직전까지의 점수 합이 주어졌을 때, 우승할 가능성이 있는 응시자의 수를 구하는 프로그램을 작성하시오.
(SCPC 실제 대회 규칙과는 관련이 없습니다.)
- 제한시간: 전체 테스트 케이스는 5개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내) 

메모리 사용제한

heap, global, static (총계) : 256MB
stack : 1MB

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 케이스의 개수 T가 주어지고,
후 차례로 T개 테스트 케이스가 주어진다. (1≤T≤5)
각각의 테스트 케이스의 첫 줄에는 응시자의 수 N 이 주어지며 ( 1≤N≤300,000 ),
다음  N 개의 줄에는 각 응시자가 마지막 라운드 전까지 받은 점수의 합을 나타내는 N 개의 자연수가 한 줄에 하나씩 주어진다.
(여기서 점수 합은 2,000,000을 넘지 않는 음이 아닌 정수이다.)

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 T는 케이스의 번호이다.
각 케이스에 대해서 우승할 가능성이 있는 응시자의 수를 출력한다.

풀이

이 문제의 경우에N의 최대값이 30만이므로, O(n^2) 미만의 시간복잡도 내에서 풀어야 한다. 

문제를 간단히 바꾸면, N명의 선수들의 누적점수가 주어지고, 마지막 경기가 이루어졌을때 1등을 할 가능성이 있는 선수의 수를 구하라는 문제다. 마지막 경기의 결과에따라 1 ~ N 의 점수가 부여된다. 

임의의 선수가 우승할 가능성이 있는지 판단하려면, 그 선수입장에서 가장 최선의 경우일때 우승할 수 있는지 판단하면 된다. 이 때, 최선의 경우란, 당연히 마지막경기에서 자신이 1위를하고, 나머지 등수는 이전경기까지의 순위의 역으로 되는 경우다. 즉, 자신이 1등을 하고, 이전경기에서 꼴찌가 2등 , 이전경기 1등이 꼴찌가 되는 경우다. 이를 위해서는 일단 이전경기까지의 순위가 필요하므로, 입력받은 점수들을 정렬해야 한다. 따라서 알고리즘의 복잡도는 적어도 O(nlogn) 이상이 된다. 비교를 기반으로 한 정렬의 시간복잡도는 절대 O(nlogn)보다 낮게 나올 수 없기 때문이다. 

정렬을 한 후, 임의의 i등의 사람입장에서 최선의 경우를 표로 표시하면 다음과 같다.

점수를 오름차순으로 정렬했을때의 순서	기존 누적점수	마지막경기 이후 최종점수
1	a(1)	a1 + (n -1)
2	a(2)	a2 + (n - 2)
3	a(3)	a3 + (n - 3)
...
j	a(j}	a(j) + (n - j)
...
i	a(i)	a(i) + n
i-1	a(i-1)	a(i-1) + (n - (i-1) +1)
...
k	a(k)	a(k)+(n - k + 1)
...
n-1	a(n-1)	a(n-1) + 2
n	a(n)	a(n)+1

즉, 문제는 "정렬된 점수로 이루어진 수열 {a(1), a(2), ... a(n)} 을 위 표의 '마지막경기 이후 최종점수' 항목의 값들로 변형시킨 수열 {b(1), b(2), ... b(n)} 의 최대값이 b(i)인 i의 갯수를 구하시오." 가 된다.

또한, 원래 수열 {a(1), a(2), ... a(n)}  이  i < j 일 떄 a(i) ≤ a(j) 이므로 k < i 인 b(k) 에 대해선 b(k) < b(i) 임이 확실하므로 비교할 필요가 없다. 따라서 이를 코드로 나타내면 다음과 같다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Solution {
	static int Answer;
	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int array[] = new int[n];
			for(int i=0;i<n;i++)
				array[i] = sc.nextInt();
			Arrays.parallelSort(array);
			int count = n;
			for(int i=0;i<n;i++) {
				for(int j=i;j<n;j++) {
					if(array[i]<array[j]-j) {
						count--;
						break;
					}
				}
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(count);
		}
	}
}

그러나, 이 코드는 100점 만점에 60점만 획득하였다. 개선을 위해 우선 알고리즘의 복잡도를 판단하기 위해 가장 중첩된 반복문을 뽑아보면 아래와 같다.

int count = n;
for(int i=0;i<n;i++) {
	for(int j=i;j<n;j++) {
		if(array[i]<array[j]-j) {
			count--;
			break;
		}
	}
}

이의 복잡도는 O(n^2) 이 나온다. 안쪽 루프들의 실행 횟수가 대충 n * (n-1) /2 정도기 때문이다. 이 문제는 O(n^2) 미만의 복잡도로 풀어야 함이 확인되었다. 즉,  위 코드를 대체한 코드는 O(nlogn) 이하여야한다는 소리다.

사실, 생각해보면 결국, 해야할 것은 a(i) + n 이 , i < j인 모든 a(j) + (n - j) 들중 최대값보다 큰지 비교하는 것이다. 따라서  i < j인 모든 a(j) + (n - j) 들중 최대값을 구하고, 이와 a(i) + n과 비교하기만 하면 된다. 다만, i < j 라는 조건이 추가되면 j와 j 사이에 종속관계가 생기고 이중 반복문이 될 수 밖에 없다. 근데, 다행이게도, k< i인 경우, b(k) = a(k) + (n-k+1) 로 a(k) + (n - k) 보다 크다. 따라서, i < j 라는 조건을 삭제하고, j 값에 상관없이 b(j) = a(j) + n - j 로 정의해도 문제에 영향을 끼치지 않는다. 

정리하면, a(j) + n - j 중 최대값을 구하고, 이를 다시 a(i) + n 과 비교하면 된다. 아래 코드는 배열의 인덱스가 0부터 시작한다는 점때문에 비교하는 값이 조금 다르다. 

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Solution {
	static int Answer;
	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int array[] = new int[n];
			for(int i=0;i<n;i++)
				array[i] = sc.nextInt();
			Arrays.parallelSort(array);
			int count = 0;
			int max=array[n-1]+1;
			for(int i=0;i<n;i++) {
				if(max<array[i]+n-(i+1)) {
					max = array[i]+n-(i+1);
				}
			}
			for(int i=0;i<n;i++) {
				if(max<array[i]+n) {
					count++;
				}
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(count);
		}
	}
}