[프로그래머스] (Swift) 순위

문제 보러가기

문제 읽기

• n 명의 권투선수들이 1대1로 대결한다.
• a가 b보다 순위가 높다면 a는 b를 항상 이긴다.
• 경기 결과에는 모순이 없다. a가 b를 이기고 b가 c를 이겼는데 c가 a를 이기는 결과는 없다.
• 경기 결과를 몇 개 잃어버려서, 전체 순위를 정확하게 매길 수 없다.
• 주어진 결과만을 가지고 순위를 확정할 수 있는 선수의 수를 구하자.

생각하기

처음에 생각했던 방법은 다음과 같다.

1. 이차원 배열에 각 선수별로 가능한 등수 [1…n] 저장해두기
2. 다른 이차원 배열에 결과 저장하면서 이겼다면 가능한 등수를 뒤에서 빼고 졌다면 앞에서 빼기
3. 가능한 등수가 하나 남은 선수 확정짓기
4. 그 선수와 관련된 선수들의 가능한 등수 정리하기
5. 바꾸는 게 없을 때까지 3, 4번 과정을 반복하기

여기서 문제는 2번이었다. a가 b를 이기는 결과가 나왔다면 a를 이긴 모두가 b를 이기고, b가 이긴 모두를 a가 이겨야 한다. 이렇게 연결되는 관계를 저장하지 못했다.
결국 두 선수 간의 관계를 알려면 다른 사람을 거쳐서 연결할 수 있는지 확인해야 했다. 이때 플로이드 와샬 알고리즘을 사용한다. i, j, k 삼중 for문을 사용해서, j에서 i를 거쳐 k로 갈 수 있는지 확인한다. n * n 배열 전체를 n번 보게 된다.

해결 방법

1. 이차원 배열을 만들어서 기본값을 전부 0으로 채워준다.
2. results를 순회하면서 array[a][b] = 1, array[b][a] = -1 로 저장한다
3. 만들어진 배열을 삼중 for문으로 순회하면서 선수들 간의 모든 관계를 저장한다
4. 각 행(각 선수)에서 0의 개수가 1이라면(자기 자신 빼고 모든 선수와의 관계가 정해졌다면) 순위를 확정할 수 있는 선수다.

다른 선수들과의 관계만 정해지면 순위를 알 수 있기 때문에 각 선수가 몇 등인지는 구할 필요 없다.

코드

import Foundation

func solution(_ n:Int, _ results:[[Int]]) -> Int {
	// 방법 1
    var score = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)

	// 방법 2
    for r in results {
        let a = r[0] - 1, b = r[1] - 1 // 1...n 을 0..<n 으로 바꾸기 위해
        score[a][b] = 1
        score[b][a] = -1
    }
    // 방법 3
    for i in 0..<n { // 중간에 끼는 선수
        for j in 0..<n { // 이기는 선수. 행
            for k in 0..<n { // 지는 선수. 열
                                // j가 i를 이기고 i가 k를 이기면 j가 k를 이긴다
                                if score[j][i] == 1 && score[i][k] == 1 {
                    score[j][k] = 1
                    score[k][j] = -1
                }
            }
        }
    }
    return score.filter{ $0.filter{ $0 == 0 }.count == 1 }.count // 방법 4
}