[Swift] [45일차] 1823_LEET (원형테이블)

1823. Find the Winner of the Circular Game

---

문제설명

1. 원형으로 사람을 순서대로 배치 (1부터 n까지)
2. 시작점 포함 , k번째있는 친구를 하나씩 없애주면서 1개남을 때까지 반복!
3. 없어진애 다음이 다음 시작점!

---

문제 풀이

1. 일단 (idx+1) % n이 순환 배열의 인덱스를 찾을 수 있을 것 같고,
2. 이게 계속해서 배열이 줄어드는 상황이니까 인덱스로 장난치면서 TRUE FALSE를 담아준 배열로 카운팅을 할것인지 말것인지로 지워진 배열을 판단할 수 있을 것 같다.

풀이하면서 변경된거는

2번 풀이가 생각보다 그렇게 쉽게 되는게 아니였다. 이거 그러면 for문으로 하나씩 넘겨짚으면서 T/F 판단을 해줘야했기에 그렇게 n번 순환돌거면 그냥 차라리 remove(at:)으로 지워주는게 낫겟다 싶어서 그런쪽으로 변경을 했다.

---

최종 제출

class Solution {
    func findTheWinner(_ n: Int, _ k: Int) -> Int {
        var arr = Array(repeating: 0, count: n).enumerated().map { $0.offset + 1 }
        var start = 0
        while arr.count > 1 {
            let nextIdx = (start + k - 1) % arr.count // 다음 인덱스
            arr.remove(at: nextIdx)
            start = nextIdx
        }
        return arr[0]
    }
}

1. 이렇게하면 지워진데로부터 시계방향으로 이동하는거는 자연스럽게 해당 인덱스가 지워진 상태에서는 그냥 그대로 start를 유지시켜주면 자동으로 원하는게 된다.
2. 그렇게 arr.count>1로 조건을 걸어줬기 때문에 이제 한개가 남았을때 arr[0]을 return !

타인의 코드

class Solution {
    func findTheWinner(_ n: Int, _ k: Int) -> Int {
       var arr = [Int]()
    var ans = 0
    
    for i in 1...n {
        arr.append(i)
    }
    
    func solve(_ arr: inout [Int], _ k: Int, _ index: inout Int, _ ans: inout Int) {
        if arr.count == 1 {
            ans = arr[0]
            return
        }
        
        index = (index + k) % arr.count
        arr.remove(at: index)
        solve(&arr, k, &index, &ans)
        
        
    }
    var index = 0
    solve(&arr, k - 1, &index, &ans)
    return ans  
    }
}

1. inout 변수써서 재귀로 하나씩 지워주는 방식을 택한 것 같다.
2. 사실상의 풀이는 while문이랑 거의 동일한 듯, 그래서 같이 분포에 속한 것 같다.