[알고리즘 풀이 분석] 프로그래머스 순위

오늘 풀어본 문제는 프로그래머스 순위 문제이다.
요즘 난 졸라 뽀로로다,, 놀고만 싶다,, 정신 못차린다 ㅜ

프로그래머스 순위

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

입출력

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

풀이

문제는 매우 간단했다. 요구사항도 바로 이해가 되었는데 막상 풀려고 하니 어떻게 해야 할지 감이 전혀 오지 않았다.

20분 정도 고민 해 보았지만 아이디어가 전혀 떠오르지 않았고 질문 사항에 있는 참고 글을 읽고 해결하였다.

이 문제를 해결하는데 있어서 가장 중요한 아이디어는 "순위를 정할 수 있다는 것을 어떻게 확인하는 것인가?" 이고 그 정답은 "나를 제외한 모든 선수와의 순위를 알 수 있을 때" 였다.

이 부분만 떠올릴 수 있었다면 풀 수 있었을까,,? ㅜ

주어지는 results 의 모든 원소를 대상으로 n x n 크기의 배열 match 를 작성 해 나간다. 이 때 배열 match[i][j] 의 의미는 i가 j를 대상으로 이겼는지 졌는지를 기록하였는데 1 = 승, -1 = 패, 0 = 기록 안됨 과 같이 기록하였다.

results[i] = [a,b] 와 같을 때 우선 match[a][b] = 1, match[b][a] = -1 과 같이 기록해나간다.

동시에 새로운 a와 b의 승패를 기록하면서 추가적으로 정해지는 결과를 함께 기록해주어야 하는데 예를 들어,

results = [[1,2],[4,5],[3,4],[2,3]] 과 같을 때 [1,2] 와 [4,5] 에 대한 작업 후 [3,4] 에서 3>4>5 와 같은 순서가 완성된다. 즉 match[3][4] = 1, match[4][3] = -1 을 기록할 때 match[3][5] = 1, match[5][3] = -1 과 같이 배열을 수정해 주어야 한다는 뜻이다.

이러한 과정은 연쇄적으로 일어날 수 있기 때문에 재귀적으로 함수를 만들어 구현하였고 재귀 함수 내에서 기록하고자 하는 칸의 값이 0일때만 (중복 방지) 재귀를 호출해 시간 초과를 피할 수 있도록 했다.

이번 문제 역시 cpp, swift 두가지로 시도하였다.

코드

c++

#include <vector>

using namespace std;

vector<vector<int>> match;
vector<int> written;

void writeMatch(int win, int lose){
    if(match[win][lose] == 0 && match[lose][win] == 0){
        match[win][lose] = 1;
        written[win] += 1;

        match[lose][win] = -1;
        written[lose] += 1;

        for (int i = 1; i < match.size(); ++i) {
            if ( i != lose && match[lose][i] == 1){
                writeMatch(win, i);
            }

            if (i != win && match[win][i] == -1){
                writeMatch(i, lose);
            }
        }
    }

    return;
}


int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    match.assign(n+1, vector<int>(n+1, 0));
    written.assign(n+1, 0);

    for(int i=0; i<results.size(); i++){
        writeMatch(results[i][0], results[i][1]);
    }

    for(int i=1; i<=n; i++){
        if(written[i] == n-1) answer++;
    }

    return answer;
}

swift

import Foundation

var match = [[Int]]()
var count = [Int]()

func writeMatch(_ win : Int, _ lose : Int) -> Void {
    if match[win][lose] == 0 && match[lose][win] == 0 {
        match[win][lose] = 1
        match[lose][win] = -1
        
        count[win] += 1
        count[lose] += 1
        
        for i in 1...match.count-1 {
            if i != lose && match[lose][i] == 1 {
                writeMatch(win, i)
            }
            
            if i != win && match[win][i] == -1 {
                writeMatch(i, lose)
            }
        }
    }
    
    return
}

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    
    match = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)
    count = [Int](repeating: 0, count: n+1)
    
    for pair in results {
        writeMatch(pair[0], pair[1])
    }
    
    var answer = 0
    for i in 1...n {
        if count[i] == n-1 {
            answer += 1
        }
    }
    
    return answer
}