문자열?_programmers_ 신고 결과 받기 [swift]

https://programmers.co.kr/learn/courses/30/lessons/92334

코딩테스트 연습 - 신고 결과 받기

 

접근 방법

1. 신고당한 사람: 신고한 사람 Dictionary를 만들자.
2. 이 때, 신고한 사람이, 똑같은 사람을 신고하면 Count == 1 이므로, 1.의 Dic의 value는 Set<String>으로 한다.
3. Dic.value.count >= k 일 때, stack에 Dic.value를 추가한다. 그렇다면 메일 받을 사람을 추가한 것.
4. stack의 String을 같은 것 끼리 분리하여, return 한다.

위의 접근방법으로 만든 코드는 정답 코드 아래의 틀린코드이다.

 

정답 코드

접근 방법과의 차이는 stack이 responseDic으로 바뀐 점이다.

id_list의 element 중 하나를 id 라 칭할 때,

stack에서 id를 분리해내는 작업을 filter를 통해 했는데, stack이 클 경우, overhead가 크다.

때문에, dictionary로 변경하였다. 물론, stack을 fastEnumerate하여 갯수를 셀 수 있다.

 

성능에 있어서 틀린 코드보다 전체적으로 빨라짐을 알 수 있다.

테스트 1 〉	통과 (0.18ms, 16.5MB)
테스트 2 〉	통과 (0.25ms, 16.5MB)
테스트 3 〉	통과 (1094.63ms, 33.9MB)
테스트 4 〉	통과 (0.38ms, 16.4MB)
테스트 5 〉	통과 (0.38ms, 16.5MB)
테스트 6 〉	통과 (9.95ms, 16.6MB)
테스트 7 〉	통과 (24.40ms, 16.9MB)
테스트 8 〉	통과 (48.88ms, 17.2MB)
테스트 9 〉	통과 (502.64ms, 24.5MB)
테스트 10 〉	통과 (470.04ms, 24.2MB)
테스트 11 〉	통과 (1042.94ms, 33.6MB)
테스트 12 〉	통과 (1.75ms, 16.5MB)
테스트 13 〉	통과 (1.54ms, 16.5MB)
테스트 14 〉	통과 (554.64ms, 24.4MB)
테스트 15 〉	통과 (959.62ms, 31.2MB)
테스트 16 〉	통과 (1.51ms, 16.6MB)
테스트 17 〉	통과 (1.59ms, 16.4MB)
테스트 18 〉	통과 (3.13ms, 16.6MB)
테스트 19 〉	통과 (5.60ms, 16.6MB)
테스트 20 〉	통과 (531.43ms, 24.6MB)
테스트 21 〉	통과 (977.77ms, 31MB)
테스트 22 〉	통과 (0.14ms, 16.6MB)
테스트 23 〉	통과 (0.13ms, 16.5MB)
테스트 24 〉	통과 (0.13ms, 16.6MB)

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var dic: [String: Set<String>] = [:] // 신고당한 사람 : 신고한 사람들
    var responseDic: [String: Int] = [:] // 메일받을 사람, 메일 수
    
    for rep in report {
        let strs = rep.components(separatedBy: " ")
        
        if dic[strs[1]] == nil {
            dic[strs[1]] = []
            dic[strs[1]]!.insert(strs[0])
        } else {
            dic[strs[1]]!.insert(strs[0])
    
        }
        
    }
    
    for info in dic {
        if info.value.count >= k {
            for receiver in info.value {
                if responseDic[receiver] == nil {
                    responseDic[receiver] = 0
                    responseDic[receiver]! += 1
                } else {
                    responseDic[receiver]! += 1    
                }
                
            }
        } 
    }
    
    var sol: [Int] = []
    
    for id in id_list {
        sol.append(responseDic[id] ?? 0)
    }
    
    return sol
}

틀린 코드

예상되는 원인 : filter하며 시간을 다 까먹는거 같다.

정확성 테스트

테스트 1 〉	통과 (0.20ms, 16.4MB)
테스트 2 〉	통과 (0.31ms, 16.6MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (0.46ms, 16.5MB)
테스트 5 〉	통과 (0.43ms, 16.4MB)
테스트 6 〉	통과 (10.34ms, 16.7MB)
테스트 7 〉	통과 (28.38ms, 17MB)
테스트 8 〉	통과 (58.85ms, 17.2MB)
테스트 9 〉	통과 (5142.49ms, 25.9MB)
테스트 10 〉	통과 (508.23ms, 24.3MB)
테스트 11 〉	통과 (7507.48ms, 36MB)
테스트 12 〉	통과 (7.01ms, 16.7MB)
테스트 13 〉	통과 (2.12ms, 16.6MB)
테스트 14 〉	통과 (6854.26ms, 26.4MB)
테스트 15 〉	통과 (1187.41ms, 31.2MB)
테스트 16 〉	통과 (2.20ms, 16.5MB)
테스트 17 〉	통과 (2.15ms, 16.7MB)
테스트 18 〉	통과 (10.82ms, 16.7MB)
테스트 19 〉	통과 (16.50ms, 16.8MB)
테스트 20 〉	통과 (5806.61ms, 26.2MB)
테스트 21 〉	실패 (시간 초과)
테스트 22 〉	통과 (0.15ms, 16.7MB)
테스트 23 〉	통과 (0.16ms, 16.6MB)
테스트 24 〉	통과 (0.14ms, 16.3MB)

채점 결과

정확성: 91.7

합계: 91.7 / 100.0

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var dic: [String: Set<String>] = [:] // 신고당한 사람 : 신고한 사람들
    
    for rep in report {
        let strs = rep.components(separatedBy: " ")
        
        if dic[strs[1]] == nil {
            dic[strs[1]] = []
            dic[strs[1]]!.insert(strs[0])
        }
        
        dic[strs[1]]!.insert(strs[0])
    }
    
    var responseStack: [String] = []
    
    for info in dic {
        if info.value.count >= k {
            responseStack.append(contentsOf: info.value)  
        } 
    }
    
    var sol: [Int] = []
    
    for id in id_list {
        sol.append(responseStack.filter{$0 == id}.count)
    }
    
    return sol
}