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

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

프로그래머스

 

2023.08.02 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

각 선수의 경기 결과들이 주어지고 몇몇 경기 결과는 분실해서 없는 상황입니다.

주어진 경기 결과들로만으로 순위를 확정할 수 있는 선수의 수를 return 해야 합니다.

 

우선 경기 결과라는 것은 결국 부모와 자식의 관계와 같습니다. 이긴 사람은 부모 진 사람은 자식에 상응합니다.

즉, 그래프의 형태를 이루게 됩니다.

 

다시 구해야하는 값에 집중해보면 순위를 확정을 할 수 있는 선수의 수를 구해야 합니다.

이때 순위를 확정한다는 것은

자신보다 순위가 높은 사람의 수 + 자신보다 순위가 낮은 사람의 수 == 자신을 제외한 전체 사람의 수

일 때를 의미합니다.

이 규칙을 떠올리는 것이 중요했습니다.

 

사실 당연한 이야기입니다. 나를 이긴 사람의 수와 내가 이긴사람의 수가 확실하다면 내 순위는 자동으로 결정됩니다.

 

예를 들어 전체 사람수가 5명이고 내가 3명을 이겼고 1명에게 졌다면 더 이상 남은 사람이 없기 때문에 자동으로 2등으로 확정됩니다.

 

그래프의 관점에서

자신보다 순위가 높은 사람의 수 == 부모 노드의 수

자신보다 순위가 낮은 사람의 수 == 자식 노드의 수

이렇게 해석할 수 있습니다.

 

이제 문제는 단순히 그래프를 탐색하며 부모 노드의 수와 자식 노드의 수를 구하는 문제로 바뀌었습니다.

 

그래프를 탐색하는 방법은 다양하지만 저는 BFS를 사용했습니다.

 

우선 그래프를 만들기 위해 딕셔너리를 사용합니다.

부모 노드와 자식 노드를 효율적으로 저장하기 위해 2개의 딕셔너리를 만들었습니다.

• loserDict ➡️ key: 선수 번호, value: key의 선수에게 패배한 선수들의 목록
• winnerDict ➡️ key: 선수 번호, value: key의 선수를 상대로 이긴 선수들의 목록

 

이제 1번부터 n번까지 선수들을 탐색하며 부모 노드의 수와 자식 노드의 수를 구하면됩니다.

이 둘의 합이 n-1이라면 해당 선수는 순위를 확정할 수 있는 선수입니다.

 

풀이

1. 큐 구현

별도의 큐 구현 없이 Swift의 기본 어레이를 사용해도 무방합니다.

public struct Queue<T> {
    
    // MARK: - Properties
    
    private var info = [T]()
        
    /// O(1)
    public var count: Int {
        self.info.count
    }
    
    /// O(1)
    public var isEmpty: Bool {
        self.info.isEmpty
    }
    
    /// O(1)
    public var peek: T? {
        self.info.first
    }
    
    // MARK: - initialization
    
    public init() {}
    
    // MARK: - Methods
    
    /// O(1)
    public mutating func enqueue(_ item: T) {
        self.info.append(item)
    }
    
    /// O(n)
    @discardableResult
    public mutating func dequeue() -> T? {
        return self.info.removeFirst()
    }
}

 

2. BFS 함수 구현

fileprivate func bfs(dict: [Int: [Int]], num: Int) -> Int {
    var queue = Queue<Int>()
    var ch = Set<Int>()
    queue.enqueue(num)
    ch.insert(num)
    
    var cnt = 0
    
    while !queue.isEmpty {
        let node = queue.dequeue()!
        
        let children = dict[node, default: []]
        
        for child in children {
            if !ch.contains(child) {
                queue.enqueue(child)
                ch.insert(child)
                cnt += 1
            }
        }
    }
    
    return cnt
}

그래프를 파라미터로 받습니다.

한번 탐색한 노드를 다시 탐색하지 않도록 Set을 만들어 탐색한 노드를 저장했습니다.

 

3. solution 함수 구현

fileprivate func solution(_ n:Int, _ results:[[Int]]) -> Int {
    var loserDict = [Int: [Int]]() // key: 선수 번호, value: key의 선수에게 패배한 선수들의 목록
    var winnerDict = [Int: [Int]]() // key: 선수 번호, value: key의 선수를 상대로 이긴 선수들의 목록
    
    for result in results {
        let winner = result[0]
        let loser = result[1]
        loserDict[winner, default: []].append(loser)
        winnerDict[loser, default: []].append(winner)
    }
    
    // 자신을 이긴 사람의 수 + 지산이 이긴 사람의 수가 n-1이면 순위를 정확하게 매길 수 있다.
    var result = 0
    for num in 1...n {
        // 자신보다 순위가 높은 사람 수
        let highRankCnt = bfs(dict: winnerDict, num: num)
        // 자신보다 순위가 낮은 사람 수
        let lowRankCnt = bfs(dict: loserDict, num: num)
        
        if highRankCnt + lowRankCnt == n-1 {
            result += 1
        }
    }
    
    return result
}

 

마무리

지금까지 Level3의 문제를 풀면서 패턴이 비슷하다는 생각이 들었습니다.

1. 문제에서 패턴을 찾아서 정답이 되는 상황 유추 (이번 문제에서는 부모 노드의 수 + 자식 노드의 수 == n-1일 때가 정답이 되는 상황!)
2. 해당 패턴을 찾을 수 있는 알고리즘 기법 떠올리기 (BFS, DFS, DP, 이분 탐색....)
3. 정답 구하기

크게 보면 위와 같은 순서로 문제를 해결했습니다.

Level 3보다 난이도가 낮은 문제들은 보통 1, 2 중에서 1개만 적용된 문제가 대부분이었습니다.

 

1번은 문제를 많이 풀다보면 점점 패턴을 찾는 시간이 줄어들 것 같고 2번의 경우에는 알고리즘 개념 공부를 꾸준히 해야하는 것 같습니다!!