프로그래머스 위클리 6주차_복서 정렬하기 c++ (정렬)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/85002

코딩테스트 연습 - 6주차_복서 정렬하기

문제 설명

복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요.

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

---

제한사항

• weights의 길이는 2 이상 1,000 이하입니다.
  • weights의 모든 값은 45 이상 150 이하의 정수입니다.
  • weights[i] 는 i+1번 복서의 몸무게(kg)를 의미합니다.
• head2head의 길이는 weights의 길이와 같습니다.
  • head2head의 모든 문자열은 길이가 weights의 길이와 동일하며, 'N', 'W', 'L'로 이루어진 문자열입니다.
  • head2head[i] 는 i+1번 복서의 전적을 의미하며, head2head[i][j]는 i+1번 복서와 j+1번 복서의 매치 결과를 의미합니다.
    • 'N' (None)은 두 복서가 아직 붙어본 적이 없음을 의미합니다.
    • 'W' (Win)는 i+1번 복서가 j+1번 복서를 이겼음을 의미합니다.
    • 'L' (Lose)는 i+1번 복사가 j+1번 복서에게 졌음을 의미합니다.
  • 임의의 i에 대해서 head2head[i][i] 는 항상 'N'입니다. 자기 자신과 싸울 수는 없기 때문입니다.
  • 임의의 i, j에 대해서 head2head[i][j] = 'W' 이면, head2head[j][i] = 'L'입니다.
  • 임의의 i, j에 대해서 head2head[i][j] = 'L' 이면, head2head[j][i] = 'W'입니다.
  • 임의의 i, j에 대해서 head2head[i][j] = 'N' 이면, head2head[j][i] = 'N'입니다.

---

입출력 예

입출력 예 설명

입출력 예 #1

• 다음은 선수들의 정보를 나타낸 표입니다.

• 본문에 서술된 우선순위를 따라 [3,4,1,2] 를 return 합니다.

입출력 예 #2

• 다음은 선수들의 정보를 나타낸 표입니다.

• 본문에 서술된 우선순위를 따라 [2,3,1] 을 return 합니다.

입출력 예 #3

• 다음은 선수들의 정보를 나타낸 표입니다.

• 본문에 서술된 우선순위를 따라 [2,1,3] 을 return 합니다.

풀이

정렬 커스텀 연습하기 좋은 문제이다.

전체적인 풀이는 조건을 잘 읽어보고 정렬을 커스텀 해놓고,

승률, 몸무게 무거운 복서 이긴 횟수, 몸무게, 복서 번호를 저장할 vector를 선언한다.

이후 모든 복서들의 NWL을 확인하며,  head2head[i][j]가 W일 경우 i가 이긴 횟수를 증가시키고,

추가로, i의 몸무게가 j의 몸무게보다 작다면, i가 자신보다 몸무게 많은 복서 이긴 횟수를 증가시킨다.

head2head[i][j]가 반대로 L이라면 j가 이긴 횟수를 증가시키고, 추가로 j의 몸무게가 i보다 작다면 j가 자신보다 몸무게 많은 복서 이긴 횟수를 증가시킨다.

만약 head2head[i][j]가 N이거나 i==j라면 스킵하고, 승률을 구할 때 사용할 전체 게임 횟수에서 제외한다.

본인은 visited[i][j]배열을 이용해 앞에서 검사한 승패 유무는 뒤에서 검사하지 않았다.

이후, 모든 선수에 대한 승률을 구해주고, 이를 커스텀 해놓은 정렬을 이용해 정렬한 후 출력한다. 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//정렬 문제
//승률 높은 순 /경기 횟수0인 사람은 승률0
//승률 같으면 자신보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서 순
//위에도 같다면 몸무게 무거운 순
//몸무게까지 같다면 번호 오름차순
//2<=weights <=1000
//45<=weights[i]<=150
//head2head 길이 weights 동일
//head2head[i]길이도 weights길이와 동일 N W L
//승률,자기보다 무거운 복서 이긴 횟수, 몸무게, 번호
vector<double> totalGame;
bool cmp(const pair<pair<double,int>,pair<int,int>> &a, const pair<pair<double,int>,pair<int,int>> &b){
    if(a.first.first==b.first.first){
        if(a.first.second==b.first.second){
            if(a.second.first==b.second.first){
                return a.second.second < b.second.second;
            }
            return a.second.first>b.second.first;
        }
        return a.first.second>b.first.second;
    }
    return a.first.first>b.first.first;
}

bool visited[1000][1000];
vector<int> solution(vector<int> weights, vector<string> head2head) {
    vector<int> answer(weights.size());
    vector<pair<pair<double,int>,pair<int,int>>> result(weights.size());    
    totalGame.resize(weights.size(),weights.size());
    for(int i=0; i<weights.size();i++){
        result[i].second = {weights[i],i+1};
        for(int j=0; j<head2head[i].size();j++){
            if(i==j || head2head[i][j]=='N'){
                totalGame[i]--;
                continue;
            }
            if(visited[i][j] || visited[j][i]) continue;
            visited[i][j]=true;
            //i가 이긴 경우
            if(head2head[i][j]=='W'){
                result[i].first.first++;
                if(weights[i]<weights[j]){
                result[i].first.second++;
                
                }
            }
            //j가 이긴 경우
            else{
                result[j].first.first++;
                if(weights[i]>weights[j]){
                result[j].first.second++;
                }
            }  
        }
    }
    //승률을 나눌 전체 게임은 N은 제외 해야 함
    for(int i=0; i<weights.size();i++){
        if(totalGame[i]!=0)
        result[i].first.first /= totalGame[i];
    }
    
    sort(result.begin(),result.end(),cmp);
    for(int i=0; i<weights.size();i++){    
        answer[i] = result[i].second.second;
    }
    return answer;
}