[S3] 백준 9017번 크로스 컨트리 C++ 구현

리뷰

 

10달만의 복수를 완료하였다, 확실히 10달 전보단 문제를 보는 시각이 많이 늘어난 것 같다.

https://www.acmicpc.net/problem/9017

 

문제 풀이

1. 참여자의 수 n과 등수 정보 배열 lst, 팀 정보 구조체 Team과 해당 배열 teams를 전역 변수로 초기화 해준다.
2. init 함수를 통해 팀 정보 teams 배열을 각 테스트 케이스 마다 초기화 해준다.
3. input 함수를 통해 n값을 받고, 특정 팀이 들어온 등수와 팀의 총원, 5번째로 들어온 등수를 기록해 준다.
4. solution함수를 통해 각 팀의 점수를 비교하여 가장 등수가 낮은 팀을 찾아준다.
5. 점수를 1부터 시작하여 팀의 총원이 6명이 이상인 경우만 등수를 기록해 준다.
6. 각 팀을 순회하며 총원이 6명 이상인 팀만 상위 4명의 등수를 참조하여 min_val, min_idx를 갱신해 준다.
7. 만약 min_val이 동일한 팀일 경우 5번째로 들어온 선수의 등수를 비교하여 우승팀을 기록한다.
8. 최종적으로 min_idx에 기록된 팀이 최종 우승팀이 된다, 해당팀을 출력해 준다.

 

참고 사항

팀 정보 구조체를 매번 테케마다 초기화 시켜주어야 다음 테케에 영향을 끼치지 않는다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;
int lst[1001];
int t, n;

struct Team {
	int cnt, index;
	vector<int> points;
};
Team teams[201];

void init() {
	for (int i = 1; i < 201; i++) {
		Team& team = teams[i];
		team.cnt = 0;
		team.index = 0;
		team.points.clear();
	}
}

void input() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int team; cin >> team;
		lst[i] = team;
		teams[team].cnt++;
		if (teams[team].cnt == 5) teams[team].index = i;
	}
}

void solution() {
	int point = 1;
	for (int i = 1; i <= n; i++) {
		if (teams[lst[i]].cnt < 6) continue;
		teams[lst[i]].points.push_back(point);
		point++;
	}
	int min_val = 1e9, min_idx = 0;
	for (int i = 1; i < 201; i++) {
		if (teams[i].cnt < 6) continue;
		vector<int>& players = teams[i].points;
		sort(players.begin(), players.end());
		int min_points = 0;
		for (int j = 0; j < 4; j++) min_points += players[j];
		if (min_val == min_points) {
			if (teams[min_idx].index > teams[i].index) min_idx = i;
		}
		else if (min_val > min_points) {
			min_val = min_points;
			min_idx = i;
		}
	}
	cout << min_idx << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;
	while (t--) {
		init();
		input();
		solution();		
	}
}