[Swift - 프로그래머스] 순위

---

🤔  풀이 과정

n명의 권투선수가 등장하고 1부터 n까지 번호를 매기는데요. 그들 간의 1대 1 매칭 결과가 results배열을 통해 주어집니다. 각각의 배열에는 승자와 패자의 원소를 순서대로 담은 배열로 주어집니다. 이 정보를 그래프로 표현하고 각각의 선수마다 DFS로 그래프 탐색하며 자신보다 강한 사람의 수, 자신보다 약한 사람의 수를 구해보고 그 합이 n - 1이 되면 순위를 알 수 있다고 판단할 수 있겠습니다.

먼저 권투 선수의 수만큼 자신보다 강한 사람의 수와 자신보다 약한 사람의 수를 저장할 배열 두 개를 만들어주고 경기결과를 바탕으로 인접 리스트 형태로 그래프를 표현해보았습니다.

오렌지색을 기준 선수라고 하였을 때 분홍색은 해당 선수보다 약한 선수들의 리스트입니다. 이제 각각의 선수를 기준으로 DFS탐색을 하게 되면 방문된 선수는 기준 선수보다 자신이 약하다는 것이므로 방문 되어질 때마다 자신보다 강한 사람의 수를 하나씩 늘려주고 DFS 호출 회수는 기준 삼았던 선수보다 약한 선수들의 수가 됩니다.  

위의 설명대로 DFS 탐색을 하며 배열을 갱신하면 다음과 같습니다.

마지막으로, 두 배열의 인덱스끼리의 합이 n - 1 이 되는 수를 세어주어서 답을 구해보았습니다. 

---

📦  문제 풀이 & 코드

import Foundation

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    var graph = [[Int]](repeating: [Int](), count: n + 1)
    var weakerThanMe = [Int](repeating: 0, count: n + 1)
    var strongerThanMe = [Int](repeating: 0, count: n + 1)
    var visited = [Bool](repeating: false, count: n + 1)
    var weakerCounter = 0
    
    func dfs(_ cur: Int) {
        visited[cur] = true
        
        for weaker in graph[cur] {
            if visited[weaker] == false {
//                print(weaker, terminator: " ")
                strongerThanMe[weaker] += 1
                weakerCounter += 1
                dfs(weaker)
            }
        }
    }

    for result in results {
        let winner = result[0]
        let loser = result[1]
        
        graph[winner].append(loser)
//        graph[winner].sort(by: <)
    }
    
    for idx in 1...n {
        visited = [Bool](repeating: false, count: n + 1)
        weakerCounter = 0
//        print("\(idx)번 선수 보다 약한 선수 ->", terminator: " ")
        dfs(idx)
//        print(" \(weakerCounter)명")
        weakerThanMe[idx] = weakerCounter
        
    }
    
    var answer = 0

    for idx in 1...n {
        if strongerThanMe[idx] + weakerThanMe[idx] == n - 1 {
            answer += 1
        }
    }
    
//    print()
//    strongerThanMe.removeFirst()
//    weakerThanMe.removeFirst()
//    print("자신보다 강한 사람의 수:", terminator: " ")
//    print(strongerThanMe)
//    print("자신보다 약한 사람의 수:", terminator: " ")
//    print(weakerThanMe)
    
    return answer
}

• 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위