소프티어 - 성적 평가 JAVA

문제

 

풀이

1. N명의 성적을 받아서 각 점수를 받은 사람이 몇명인지 카운팅 한다.

2. 각 점수의 누적합을 구한다.

3. 누적합을 통해 해당 점수가 몇등인지 계산한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

		int N = Integer.parseInt(in.readLine());
		
		// 사람들의 성적을 저장
		int[][] scores = new int[4][N];
		
		// 성적을 count
		int[][] contest = new int[4][3001];

		for (int i = 0; i < 3; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				int score = Integer.parseInt(st.nextToken());
				scores[i][j] = score;
				scores[3][j] += score;
				contest[i][score]++;
			}
		}

		for(int i=0;i<N;i++) {
			int score = scores[0][i] + scores[1][i] + scores[2][i];
			contest[3][score]++;
		}

		int[][] sum = new int[4][3001];
		// 누적합을 구한다.
		for (int i = 0; i < 4; i++) {
			for (int j = 3000; j >= 0; j--) {
				if (j == 3000) {
					sum[i][j] = contest[i][j];
				} else {
					sum[i][j] = sum[i][j + 1] + contest[i][j];
				}
			}
		}

		for (int i = 0; i < 4; i++) {
			// 순위를 출력
			for (int j = 0; j < N; j++) {
				int score = scores[i][j];

				int order;
				if (score == 3000) {
					order = 1;
				} else {
					order = sum[i][score + 1] + 1;
				}
				sb.append(order).append(" ");
			}
			sb.append("\n");
		}

		System.out.println(sb);

	}
}

 

ETC

위 방법의 시간 복잡도는
누적합 구성에 O ( K ) 가 들고 (K는 점수의 범위)
등수 확인에 O ( 1 ) 이 들기 때문에 K 의 범위가 작다면 효율적 이지만 K의 범위가 크다면 비효율적일 수 있다.