[코딩 테스트] 소프티어(Softeer) 연습 문제 - 성적평가

코딩 테스트를 위한 소프티어(Softeer) 연습 문제 중 성적평가 문제를 풀어보았다.

소프티어에서 처음으로 풀어보는 level3이며 인증평가(5차) 기출문제여서 조금 시간을 들여서 풀어보았다.

 

연습 문제 - 성적평가

• 난이도 : level 3
• 정답률 : 37%

 

https://softeer.ai/practice/info.do?idx=1&eid=1309 

Softeer

 

문제 해설

N명 (10만)이 3개의 대회에 참가한다. 참가자들은 0~1000의 점수를 획득하고 동점이 있을 수도 있다. 이 점수를 통해 높은 점수부터 등수가 결정되고, 공동 순위도 나타난다. 만약 공동 1등이 나왔다면 그다음은 2등이 아니라 3등이 될 것이다. 문제에서는 "나보다 점수가 큰 사람"의 수를 세어 1을 더한 것이 자신의 등수가 된다고 표현한다. 또한 3개의 대회에서 얻은 점수의 총합에 따른 최종 등수도 나온다. 입력과 출력이 다소 귀찮아서 조금 오래 걸리기도 했다. 나는 역시나 priority queue를 활용해서 구현했다. 즉 각 3개의 대회의 queue를 3개 만들고, 또 3개 대회의 합의 queue를 한 개 더 만들어서 총 4개를 만들었다. 동일한 등수를 처리하는 부분이 다소 복잡하게 되었다. 만약 queue를 사용하지 않는다면 문제에서 힌트를 준 "나보다 점수가 큰 사람"의 수를 세는 방식을 활용해 볼 수 있을 것 같다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Node {
	int s1, s2, s3;
};
#define maxN 100000 + 10
Node node[maxN];
int result[4][maxN];
struct pqNode {
	int id, score;
	pqNode(int i, int s) {
		id = i, score = s;
	}
};
struct comp {
	bool operator()(pqNode a, pqNode b) {
		if (a.score >= b.score) {
			return false;
		} 
		return true;
	}
};
void calculate(priority_queue<pqNode, vector<pqNode>, comp> pq, int i) {
	int num = 1;
	int prev = -1;
	int prev_num = 1;
	while (!pq.empty()) {
		int s = pq.top().score;
		int id = pq.top().id;
		if (prev != s) {
			result[i][id - 1] = num;
			prev_num = result[i][id - 1];
		}
		else {
			result[i][id - 1] = prev_num;
		}
		num++;
		prev = s;
		pq.pop();
	}
}
int main(int argc, char** argv)
{
	int N;
	cin >> N;
	priority_queue<pqNode, vector<pqNode>, comp> pq1, pq2, pq3, pq4;
	for (int i = 1; i <= N; i++) {
		int data;
		cin >> data;
		node[i].s1 = data;
		pq1.push(pqNode(i, data));
	}
	for (int i = 1; i <= N; i++) {
		int data;
		cin >> data;
		node[i].s2 = data;
		pq2.push(pqNode(i, data));
	}
	for (int i = 1; i <= N; i++) {
		int data;
		cin >> data;
		node[i].s3 = data;
		pq3.push(pqNode(i, data));
	}

	for (int i = 1; i <= N; i++) {
		pq4.push(pqNode(i, node[i].s1 + node[i].s2 + node[i].s3));
	}

	calculate(pq1, 0);
	calculate(pq2, 1);
	calculate(pq3, 2);
	calculate(pq4, 3);

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < N; j++) {
			cout << result[i][j] << ' ';
		}
		cout << endl;
	}
}

 

결론

입출력과 등수를 카운팅하는 방식에서 다소 복잡했고 구현량이 조금 필요해서 1시간~2시간 정도 걸린 것 같다. 실제 시험에서 1시간 내 풀이를 권장한다고 하는 것 같은데 좀 더 분발해야 할 것 같다.