[swift] 프로그래머스 - 신고 결과 받기

프로그래머스

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

 - id_list 순서대로 정지시킨 Id의 횟수를 리턴해야 합니다.

- 중첩되는 신고는 무효입니다.

- k번 신고당하면 아이디가 정지됩니다.

- 10000ms시간 안에 문제를 풀 수 있어야 합니다.

 

 

---

 

첫 번째 풀이(실패)

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    let reportArr = Set(report).map { $0.split(separator: " ").map { String($0) } }
    var idDic = [String: [String]]()
    var banDic = [String: Int]()
    var result = Array(repeating: 0, count: id_list.count)

    for i in reportArr {
        idDic[i[0]] = (idDic[i[0]] ?? []) + [i[1]]
        banDic[i[1]] = (banDic[i[1]] ?? 0) + 1
    }

    let ban = banDic.filter { $0.1 >= k }.keys
    result = id_list.map { i in
        var count = 0
        for j in ban {
            if let id = idDic[i] {
               if id.contains(j) { count += 1 }
            }
        }
        return count
    }
    return result
}

 

케이스 3,21번이 시간제한에 걸렸습니다.

id_list.map 반복 안에서 ban을 중첩반복 하는 게

시간초과의 원인이라고 생각했습니다.

 

---

 

두 번째 풀이(성공)

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    
    var idDic = [String: [String]]()
    var result = Array(repeating: 0, count: id_list.count)
    
    for i in Set(report) {
        let temp = i.split(separator: " ").map { String($0) }
        idDic[temp[1]] = (idDic[temp[1]] ?? []) + [temp[0]]
    }
    
    let banDic = Dictionary(grouping: idDic.filter { $0.1.count >= k }.values.flatMap { $0 }) { $0 }
    
    for i in id_list.enumerated() {
        if banDic[i.element] != nil {
            result[i.offset] = banDic[i.element]!.count
        }
    }
    return result
}

 

최대한 중첩반복을 없애고자 노력했습니다.

 

idDic의 key값에는 신고당한 사람을 넣고

value값에는 해당 key를 신고한 사람을 넣었습니다.

 

시간제한을 줄였던 핵심은

 

result를 id_list의 count만큼 0으로 채운 배열로 만들어 줬고

 

id_list와 result는 정확히 index를 공유하기 때문에

 

중첩반복 없이 id_list를 탐색하며

banDic에 있는 신고 성공 횟수를

result에 바로 쏴줄 수 있었습니다.

 

해당 풀이는 시간제한에 걸렸던

케이스 3,21번 모두 1000ms안으로 성공했습니다.

 

---