문제
복서 정렬하기
풀이
정렬 조건
- 전체 승률이 높은 복서의 번호가 앞쪽으로 갑니다. 아직 다른 복서랑 붙어본 적이 없는 복서의 승률은 0%로 취급합니다.
- 승률이 동일한 복서의 번호들 중에서는 자신보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서의 번호가 앞쪽으로 갑니다.
- 자신보다 무거운 복서를 이긴 횟수까지 동일한 복서의 번호들 중에서는 자기 몸무게가 무거운 복서의 번호가 앞쪽으로 갑니다.
- 자기 몸무게까지 동일한 복서의 번호들 중에서는 작은 번호가 앞쪽으로 갑니다.
알고리즘
1. 정렬 조건에 맞춰 input 데이터(weights, head2head)를 새로운 배열에 할당한다.
- 열: [승률, 자신보다 무거운 복서를 이긴 횟수, 몸무게, 번호]
- 행: 각 복서의 데이터
vector<vector<float>> all(weights.size(), vector<float>(4));
2. 배열에 데이터를 문제의 조건에 맞추어 넣어준다.
- 승률
(위 테이블에서 보는 것처럼 승률 계산시에 곱하기 100은 생략함. 승률 정렬 시에 상관 없기 때문에)
승률 = '이긴 횟수 / 경기 수' 라고 쉽게 생각할 수 있지만, 여기서 '경기 수'가 중요하다.
보통은 '경기 수 = weights.size()-1 혹은 head2head[0].size()-1'로 여길 가능성이 크다.
하지만 이 문제에서 승률 = 이긴 횟수 / (이긴 횟수 + 진 횟수) 으로 계산해야 한다.
위와 같이 각 복서의 경기 횟수가 각각 다를 수 있기 때문이다.
이 부분이 테스트 케이스에서는 바로 알아차릴 수 있게 주어지지 않았기 때문에 조심해야할 부분이라고 할 수 있다.- 자신보다 무거운 복서를 이긴 횟수
for (int i = 0; i < all.size(); i++) { int bigger_win = 0; //자신보다 무거운 사람 이긴 횟수 for (int k = 0; k < head2head[i].size(); k++) { //ex) head2head[i].size()=4고, i=0이라면 //ex) weights[0~4] > weights[0] if (weights[k] > weights[i]) //자신보다 무거운 사람 이긴 횟수 + 1 bigger_win++; } }위의 if문을 보자.
weights[k] = 모든 복서의 몸무게를 순회
weights[i] = 현재 데이터를 넣어줄 복서 i의 몸무게
여기서 k=i가 되어 자기 자신과 비교하는 경우가 있지만, 같은 몸무게는 고려하지 않아도 되므로 상관없다.
- 몸무게, 번호
순서에 맞게 넣어주면 된다.3. 정렬
이제 데이터는 모두 새로운 배열에 깔끔하게 넣어줬으므로 정렬 조건에 맞춰 정렬만 해주면 된다.
1순위: <내림차순>승률
2순위: <내림차순>자신보다 무거운 복서를 이긴 횟수
3순위: <내림차순>몸무게
4순위: <오름차순>선수 번호
여기서는 STL의 algorithm 헤더에서 sort() 메소드를 사용하여 정렬 조건을 새로 만들어준다.//정렬 조건 bool cmp(vector<float> a, vector<float> b) { // 승률이 같다면 -> 2번 조건 if (a[0] == b[0]) { // 자신보다 무거운 사람 이긴 횟수가 같다면 -> 3번 조건 if (a[1] == b[1]) { // 몸무게가 같다면 -> 4번 조건 if (a[2] == b[2]) // 4. 번호가 작은 순 (번호는 같은 경우가 없다) return a[3] < b[3]; // 3. 몸무게가 큰 순 else return a[2] > b[2]; } // 2. 1이 같다면 -> 자신보다 무거운 사람 이긴 횟수 else return a[1] > b[1]; } // 1. 승률 else return a[0] > b[0]; }
코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(vector<float> a, vector<float> b)
{
if (a[0] == b[0])
{
if (a[1] == b[1])
{
if (a[2] == b[2])
return a[3] < b[3];
else
return a[2] > b[2];
}
else
return a[1] > b[1];
}
else
return a[0] > b[0];
}
vector<int> solution(vector<int> weights, vector<string> head2head)
{
vector<int> answer(weights.size());
vector<vector<float>> all(weights.size(), vector<float>(4));
for (int i = 0; i < all.size(); i++)
{
float lose = 0;
float win = 0;
int bigger_win = 0;
for (int k = 0; k < head2head[i].size(); k++)
{
if (head2head[i][k] == 'W')
{
win++;
if (weights[k] > weights[i])
bigger_win++;
}
if (head2head[i][k] == 'L')
lose++;
}
all[i][0] = (win + lose) > 0 ? win / (win + lose) : 0;
all[i][1] = bigger_win;
all[i][2] = weights[i];
all[i][3] = i + 1;
}
sort(all.begin(), all.end(), cmp);
for (int i = 0; i < answer.size(); i++)
answer[i] = all[i][3];
return answer;
}주석코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//정렬 조건
bool cmp(vector<float> a, vector<float> b)
{
// 승률이 같다면 -> 2번 조건
if (a[0] == b[0])
{
// 자신보다 무거운 사람 이긴 횟수가 같다면 -> 3번 조건
if (a[1] == b[1])
{
// 몸무게가 같다면 -> 4번 조건
if (a[2] == b[2])
// 4. 번호가 작은 순 (번호는 같은 경우가 없다)
return a[3] < b[3];
// 3. 몸무게가 큰 순
else
return a[2] > b[2];
}
// 2. 1이 같다면 -> 자신보다 무거운 사람 이긴 횟수
else
return a[1] > b[1];
}
// 1. 승률
else
return a[0] > b[0];
}
vector<int> solution(vector<int> weights, vector<string> head2head)
{
vector<int> answer(weights.size());
// 행 길이: input으로 받아질 weights.size() -> 복서 수
// 열: [승률, 자신보다 무거운 사람 이긴 횟수, 몸무게, 번호]
vector<vector<float>> all(weights.size(), vector<float>(4));
//복서 수만큼 반복
for (int i = 0; i < all.size(); i++)
{
float lose = 0;
float win = 0;
int bigger_win = 0; //자신보다 무거운 사람 이긴 횟수
//각 복서의 head2head 만큼 반복
for (int k = 0; k < head2head[i].size(); k++)
{
if (head2head[i][k] == 'W')
{
//이긴 횟수 + 1
win++;
//ex) head2head[i].size()=4고, i=0이라면
//ex) weights[0~4] > weights[0]
if (weights[k] > weights[i])
//자신보다 무거운 사람 이긴 횟수 + 1
bigger_win++;
}
if (head2head[i][k] == 'L')
//진 횟수 + 1
lose++;
}
//경기 수가 0보다 크다면 all[i][0] = 승률 = 이긴 횟수/(이긴 횟수 + 진 횟수)
//경기 수가 0과 같다면 all[i][0] = 승률 = 0% -> 문제의 1번 조건에서 명시
all[i][0] = (win + lose) > 0 ? win / (win + lose) : 0;
//all[i][1] = 자신보다 무거운 사람 이긴 횟수
all[i][1] = bigger_win;
//all[i][2] = 몸무게
all[i][2] = weights[i];
//all[i][3] = 선수 번호
all[i][3] = i + 1;
}
cout << "[정렬 전]\n";
cout << "승률 BigWin 몸무게 번호\n";
for (int i = 0; i < all.size(); i++)
{
for (int j = 0; j < all[i].size(); j++)
cout << all[i][j] << " ";
cout << endl;
}
cout << endl;
// 문제의 정렬 조건에 따라 정렬
sort(all.begin(), all.end(), cmp);
cout << "[정렬 후]\n";
cout << "승률 BigWin 몸무게 번호\n";
for (int i = 0; i < all.size(); i++)
{
for (int j = 0; j < all[i].size(); j++)
cout << all[i][j] << " ";
cout << endl;
}
cout << endl;
//return 값 = 선수 번호 = all[i][3]
for (int i = 0; i < answer.size(); i++)
answer[i] = all[i][3];
return answer;
}
int main()
{
vector<int> weights1 = {50, 82, 75, 120};
vector<string> head2head1 = {"NLWL", "WNLL", "LWNW", "WWLN"};
vector<int> weights2 = {145, 92, 86};
vector<string> head2head2 = {"NLW", "WNL", "LWN"};
vector<int> weights3 = {60, 70, 60};
vector<string> head2head3 = {"NNN", "NNN", "NNN"};
vector<int> answer = solution(weights1, head2head1);
cout << "answer: ";
for (int i : answer)
cout << i << ", ";
}테스트 케이스 출력
[정렬 전]
승률 BigWin 몸무게 번호
0.333333 1 50 1
0.333333 0 82 2
0.666667 2 75 3
0.666667 0 120 4
[정렬 후]
승률 BigWin 몸무게 번호
0.666667 2 75 3
0.666667 0 120 4
0.333333 1 50 1
0.333333 0 82 2
answer: 3, 4, 1, 2,여담
대학교에서 보내는 마지막 학기가 시작하니 이거저거 할게 너무 많아서 포스팅 할 시간을 쉽게 낼 수가 없다...
흥미롭게 푼 문제나 C++ 공부 내용도 있어서 포스팅하고 싶지만 우선순위가 밀리다보니 다른 것들을 우선하게 되버려서 마음 한켠이 불안하다.
이번 포스팅은 1시간 30분정도 소요된 것 같은데, 사실 문제 자체에 크게 어려운 부분이 있다기보다는 쉽게 헷갈릴 수 있는 부분이나 데이터 테이블을 시각화해서 쉽게 보여주려다 보니 공이 많이 들었다.
포스팅을 하면서 느끼지만 문제를 풀 때보다 문제를 설명할 때가 체감상 3배정도 어려운거 같다.
아무래도 내 생각을 다른 이들이 모두 납득 가능하도록 말로 풀어내야 하니 그런 듯 싶다.
게임... 만들지 않겠는가..