[코테] Softeer Lv.3 - 성적 평가

문제 요약

N명이 참가하는 대회 3번 개최
N명의 성적이 한 줄에 공백으로 주어질 때, 각 대회별 & 종합 등수를 출력하는 문제

입력형식

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

출력형식

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

해결 방법

처음 생각한 방법은 아래와 같은데

1. 한 대회의 성적을 리스트에 대입한 후, 정렬한다.
2. 정렬한 배열을 돌면서 등수를 계산하여 같은 위치에 대입한다.
3. 한 대회의 1번 참가자부터 전체 리스트를 순차적으로 돌면서 자기 등수를 찾는다.

과정 3에서 $n$개의 항목에 대해 각각 최대 $n-i$번 탐색해야 해서 시간 복잡도가 $O(n^2)$ 이었다. 제한 시간을 초과하는 문제가 생겼다.

따라서, 과정 3의 탐색을 이진 탐색으로 구현하였다.

• 1 : 리스트 정렬
  <algorithm> 헤더의 sort() 함수를 이용했다.

	// 정렬된 리스트 생성
	int* sorted = new int[N]();
	int* prize_list = new int[N]();
	for (int i=0; i<N; i++)
		sorted[i] = l[i];
	sort(sorted, sorted+N, greater<int>());

• 2 : 등수 계산
  겹치는 등수를 세기 위한 cnt, 전체 등수를 계산하기 위한 prize를 만들고 리스트를 돌면서 조건에 따라 등수를 대입했다.

	// 등수 테이블 채우기
	int cnt;
	int prize = 1;
	bool cnt_start = false;
	for (int i=0; i<N; i++) {
		if (cnt_start) {
			// 이전 인덱스와 다르면
			if (sorted[i] != sorted[i-1]) {
				// 이전 인덱스의 값 = prize
				prize_list[--i] = prize;
				// prize를 업데이트하고, 다시 카운트 시작
				prize += cnt;
				cnt_start = false;
			}
			// 이전 인덱스와 같으면
			else {
				// 이전 인덱스의 값 = prize
				prize_list[i-1] = prize;
				// 카운트 추가
				cnt++;
			}
		}
		else {
			cnt = 1;
			cnt_start = true;
		}
	}
	// 마지막
	prize_list[N-1] = prize;

• 3 : 각 참가자마다 등수 탐색
  이진 탐색으로 해당 참가자의 등수를 찾았다.

	int SearchList(int* l, int key) {
		int low = 0;
		int high = N-1;
		int mid;

		while (low <= high) {
			mid = (low + high) / 2;
			if (key == l[mid]) {
				return mid;
			}
			else if (key < l[mid]) {
				low = mid + 1;
			}
			else if (key > l[mid]) {
				high = mid - 1;
			}
		}
	}

얻어가는 것

• 이진 탐색 구현 (유사코드)

    binarySearch() {
        low = 0
        high = N-1

        while (low <= high) {
            mid = (low + high) / 2
            if (key == list[mid])
                return mid
            else if (key > list[mid])
                low = mid + 1
            else if (key < list[mid])
                high = mid - 1
        }
    }