[프로그래머스][C++] 위클리 챌린지 6주차 복서 정렬하기

WestCoast·2021년 9월 8일
0

코딩테스트 풀이

목록 보기
8/13

문제

복서 정렬하기

풀이

정렬 조건

  1. 전체 승률이 높은 복서의 번호가 앞쪽으로 갑니다. 아직 다른 복서랑 붙어본 적이 없는 복서의 승률은 0%로 취급합니다.
  2. 승률이 동일한 복서의 번호들 중에서는 자신보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서의 번호가 앞쪽으로 갑니다.
  3. 자신보다 무거운 복서를 이긴 횟수까지 동일한 복서의 번호들 중에서는 자기 몸무게가 무거운 복서의 번호가 앞쪽으로 갑니다.
  4. 자기 몸무게까지 동일한 복서의 번호들 중에서는 작은 번호가 앞쪽으로 갑니다.

알고리즘

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배정도 어려운거 같다.
아무래도 내 생각을 다른 이들이 모두 납득 가능하도록 말로 풀어내야 하니 그런 듯 싶다.

profile
게임... 만들지 않겠는가..

0개의 댓글