[C#] 순위

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191

풀이 후기

1. 분석 못 함

뭔가 트리인 거 같아서 그림을 좀 그리다가 왜 테스트 케이스 1의 정답이 2가 나오는 거지? 라는 생각이 들었다. 정확한 순위를 이해하지 못해서 단순히 노드 바꿔치기로 푸는 건가 삽질을 좀 하다가 질문하기 글 읽고 와서 드디어 이해했다.

2. 컨닝 후

정확한 순위의 조건은 다음과 같다는 걸 시행착오 끝에 깨달았다.

• 모든 상대방과의 대전 결과가 존재해야 한다.

• 대전 결과는 직접 얻지 않아도 된다.

• 즉, 내가 AvsB 했는데 A가 이겼으면, A는 B가 승리했던 상대방에게 전부 다 승리한 것.

• B는 A가 패배했던 상대방에게 전부 다 패배한 것.

• 추가로 B는 자신이 승리했던 상대방들에게 가서 ＇님보다 A가 더 쌔다.＇ 라고 전달함.

• A는 자신이 패배했던 상대방들에게 가서 ＇B보다 님이 더 쌔다.＇ 라고 전달함.

  그러니까 이런 식으로 유추가 가능한 대전들을 갱신해서 대전 결과가 전부 있으면 등수를 알 수 있다. 그래서 저런 식으로 기록을 추가했더니 풀기는 했음...

3. 실행 결과

3초 6초 7초 이러는 걸 보니까 이상한 풀이 같지만 더 풀 힘이 없어서 포기.

4. 코드

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public static List<Player> allMatchPlayers = new List<Player>();
    public static Player[] players;
    public static int matches = 0;

    public class Player{
        public int index;
        public int[] match;
        public int matchCount = 0;
        public int win = 0;
        public int lose = 0;

        public Player(int i, int n){
            index = i;
            match = new int[n];
        }
        
        public void Win(int n)
        {
            if (match[n] != 0) return;
            
            match[n] = 1;
            win++;
            matchCount++;
            if(matchCount == matches){
                allMatchPlayers.Add(this);
            }
        }
        
        public void Lose(int n)
        {
            if (match[n] != 0) return;
            
            match[n] = -1;
            lose++;
            matchCount++;
            if(matchCount == matches){
                allMatchPlayers.Add(this);
            }
        }

        public void UpdateMatch(int n, bool isWin)
        {
            var otherMatches = players[n].match;
            
            for (var i = 0; i < otherMatches.Length; i++)
            {
                if (i == index || match[i] != 0) continue;
                
                if(isWin && otherMatches[i] == 1)
                {
                    Win(i);
                }

                if(!isWin && otherMatches[i] == -1)
                {
                    Lose(i);
                }
            }
        }

        public void UpdateToOther(bool isWin)
        {
            if (isWin)
            {
                for (var i = 0; i < match.Length; i++)
                {
                    if (index != i && match[i] == -1)
                    {
                        players[i].UpdateMatch(index, true);
                    }
                }
            }
            else
            {
                for (var i = 0; i < match.Length; i++)
                {
                    if (index != i && match[i] == 1)
                    {
                        players[i].UpdateMatch(index, false);
                    }
                }
            }
        }
    }
    
    public int solution(int n, int[,] results) {
        players = new Player[n];
        matches = n - 1;
        
        for(int i = 0; i < n; i++){
            players[i] = new Player(i, n);
        }
        
        for(int i = 0; i < results.GetLength(0); i++){
            var a = results[i, 0] - 1;
            var b = results[i, 1] - 1;
            players[a].Win(b);
            players[b].Lose(a);
            players[a].UpdateMatch(b, true);
            players[b].UpdateMatch(a, false);
            players[a].UpdateToOther(true);
            players[b].UpdateToOther(false);
            var d = 1;
        }

        return allMatchPlayers.Count;
    }
}

가장 해답에 가까운 풀이는 플로이드 같던데 다익스트라든 플로이드든 배웠는데 하나도 기억나지 않는다. 나중에 복습해야 겠다.