[Swift] 프로그래머스 순위

 

Problem

 

코딩테스트 연습 - 순위

---

Solution

 

이번 문제는 플로이드 와샬 으로 풀어야 하는 그래프 문제입니다.

 

1. 모든 승부를 저장할 이중 배열을 만든다.

 

1부터 n까지의 선수들의 승부를 담을 이중 배열을 만들어줍니다.

 

1부터 시작하므로 n+1 크기로 값을 0으로 가지고 있는 배열을 n+1개를 만들어줍니다.

 

n+1개씩을 만들어주는 이유는 0번 인덱스를 무시하기 하기 위해서입니다.

 

(win 배열을 참고해주세요)

 

2. results를 순회하여 승부에 대한 값을 저장한다.

 

results안에 있는 값 중 0번째는 이긴 사람 1번째는 진 사람이므로 

 

승부를 담는 배열 [result[0]][result[1]] 의 값을 1로 바꿔줍니다.

 

0은 모르는 상태 1은 이긴 상태로 저장하겠습니다.

 

(results.forEach를 확인해주세요!)

 

3. 플로이드 와샬으로 중간에 있는 값을 체크해준다.

 

i,j,k 3중 for문을 만들어 i와 k의 중간에 있는 j가 k한테 지는지 이기는 체크해줍니다.

 

만약 i가 j를 이겼고 k가 i를 이겼다면 k는 j를 이길 수 있습니다.

 

고로 승부를 담는 배열의 [k][j] 번째를 1로 바꿔줍니다.

 

( checkMiddleByFloyd 함수를 참고해주세요!)

 

4. 순위를 알 수 있는 선수의 수를 계산해 반환한다.

 

1부터 n까지 순회를 하는 이중 for문을 만들어 모든 선수의 승부를 순회합니다.

 

i 선수와 j선수의 승부를 알기 위해선 승부를 담는 배열에서 i가 j를 이겼거나 j가 i를 이겼다면 알 수 있을 것입니다.

 

즉 [i][j]가 1이거나 [j][i]가 1이라면 알 수 있는 상태입니다.

 

이렇게 알 수 있는 상태가 n에서 자신의 뺀 값 즉, n-1이라면 모든 선수와의 승부를 알 수 있으므로 순위를 알 수 있습니다.

 

모두 순회를 하면서 이렇게 모든 선수와의 승부를 알 수 있는 선수의 수를 반환해줍니다.

 

( canKnowRankCount 함수를 참고해주세요! )

---

Source Code

 

	import Foundation
	func solution(_ n:Int, _ results:[[Int]]) -> Int {
	//누가 누굴 이겼는지 확인할 이중배열
	var win:[[Int]] = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
	//result의 0번째는 1번쨰를 이긴 것이므로 1이라고 체크해줌
	results.forEach{ win[$0[0]][$0[1]] = 1 }
	//중간에 있는 값을 플로이드로 알아낸다.
	checkMiddleByFloyd(win: &win, n: n)
	//순위를 알수있는 것의 갯수를 반환해준다.
	return canKnowRankCount(results: results, win: win, n: n)
	}
	//i,j,k를 두고 k가 j를 이길 수 있는 경우를 체크해준다.
	func checkMiddleByFloyd(win:inout [[Int]],n:Int) {
	for i in 1...n {
	for j in 1...n {
	for k in 1...n {
	//만약 i가 j를 이겼고 k가 i를 이겼다면
	if win[i][j] == 1 && win[k][i] == 1 {
	//k는 j를 이길 수 있다.
	win[k][j] = 1
	}
	}
	}
	}
	}
	func canKnowRankCount(results:[[Int]],win:[[Int]],n:Int) -> Int {
	//전체 갯수
	var total:Int = 0
	for i in 1...n {
	//i와 j의 승부를 알 수 있는 갯수
	var count:Int = 0
	for j in 1...n {
	//만약 i가 j한테 졌거나 이겼다면
	if win[i][j] == 1 || win[j][i] == 1 {
	//승부를 알 수 있으므로 +1
	count += 1
	}
	}
	//count가 n-1이라면 모든 승부를 알 수 있으므로
	if count == n-1 {
	//토탈을 +1
	total += 1
	}
	}
	//토탈을 반환
	return total
	}

view raw 순위.swift hosted with ❤ by GitHub

---

1차 풀이

 

처음엔 누가 누굴 이겼고 졌는지만 담고 

 

이긴 사람과 진 사람을 합쳐서 자신을 뺀 모든 사람이 담겨있다면 순위를 알 수 있겠지라고 엄청 쉬운 문제네 하고 풀었는데...

 

누가 누굴 이기고 질때마다 값이 바뀌는데 이러면 모든 값이 바뀌어야 했다.

 

그래서 결국 구글링을 통해서 플로이드 와샬로 풀어야한다는 것을 알게됨...

import Foundation

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    
    var win:[[Int]] = (0...n).map{[$0]}
    var lose:[[Int]] = (0...n).map{[$0]}
    var answer:Int = 0
    
    results.forEach{
        win[$0[0]].append($0[1])
        lose[$0[1]].append($0[0])
    }

    for i in 1..<win.count {
        let count = Set((win[i].map{win[$0]} + lose[i].map{lose[$0]}).flatMap{$0}).count
        if count == n {
           answer += 1
        }
    }
    
    return answer
}

---

Reference 

 

이 분의 블로그를 참고했습니다.

 

[C++, Swift][프로그래머스] 순위