프로그래머스

1. 문제설명

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
(자세한 내용은 위 링크 참고)

2. 제안 사항

제한사항

• 2 ≤ id_list의 길이 ≤ 1,000
  • 1 ≤ id_list의 원소 길이 ≤ 10
  • id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
  • id_list에는 같은 아이디가 중복해서 들어있지 않습니다.
• 1 ≤ report의 길이 ≤ 200,000
  • 3 ≤ report의 원소 길이 ≤ 21
  • report의 원소는 "이용자id 신고한id"형태의 문자열입니다.
  • 예를 들어 "muzi frodo"의 경우 "muzi"가 "frodo"를 신고했다는 의미입니다.
  • id는 알파벳 소문자로만 이루어져 있습니다.
  • 이용자id와 신고한id는 공백(스페이스)하나로 구분되어 있습니다.
  • 자기 자신을 신고하는 경우는 없습니다.
• 1 ≤ k ≤ 200, k는 자연수입니다.
• return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

3. 입출력 예

id_list	report	k	result
["muzi", "frodo", "apeach", "neo"]["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]	2	[2,1,1,0]
["con", "ryan"]	["ryan con", "ryan con", "ryan con", "ryan con"]	3	[0,0]

4. 풀이 과정

첫번째 시도는 실패했다.

문제는 결국 신고한 유저의 목록을 받고 그 유저가 신고한 유저들이 k이상 신고를 받게 되면 정지가 되고 그 유저를 신고한 유저리스트에 값을 증가시키면 된다.

그래서 dictionary를 이용하여
3가지 dictionary를 만들었다.

하나는 유저별로 유저가 신고한 array를 가진 것
하나는 유저별로 신고당한 횟수
하나는 유저별로 신고한 유저가 정지당한 횟수

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var dic_report : [String : [String]] = [:] 
    var dic_value : [String : Int] = [:]
    var dic_result : [String : Int] = [:]
    var result : [Int] = []
    
    for i in id_list{
        dic_report[i] = []
        dic_value[i] = 0
        dic_result[i] = 0
    }
    
    for i in report
    {
        let report_id = String(i.split(separator:" ")[0])
        let stop_id = String(i.split(separator: " ")[1])
        
        if !dic_report[report_id]!.contains(stop_id){
            dic_report[report_id]!.append(stop_id)
            dic_value[stop_id]! += 1
        }

    }
    
    for (key,value) in dic_value{
        if k <= value{
            for (key_report, value_report) in dic_report{
                if value_report.contains(key){
                    dic_result[key_report]! += 1
                }
            }
        }
    }
    
    for i in id_list{
        result.append(dic_result[i]!)
    }
    
    return result
}

결과는 시간초과로 실패이다.

n의 범위가 id_list의 경우에는 2 <= id_list <= 1,000이지만
report의 길이는 1 <= report <= 200,000여서 report를 다루는 경우 O(NlogN)인 알고리즘을 설계해야 한다.

중간에 복잡도가 for문을 두번 사용하면서 O(N^2)의 복잡도가 만들어져서 실패했다.

그래서 MN정도는 가능할거 같아서 더욱 줄이는데는 성공했으나 21번에서는 런타임 에러와 여전히 3번은 시간초과였다.

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var dic_report : [String : [String]] = [:] 
    var dic_value : [String : Int] = [:]
    var dic_result : [String : Int] = [:]
    var stop_list : [String] = []
    var result : [Int] = []
    
    for i in id_list{
        dic_report[i] = []
        dic_value[i] = 0
        dic_result[i] = 0
    }
    
    for i in report
    {
        let report_id = String(i.split(separator:" ")[0])
        let stop_id = String(i.split(separator: " ")[1])
        
        if !dic_report[report_id]!.contains(stop_id){
            dic_report[report_id]!.append(stop_id)
            dic_value[stop_id]! += 1
        }

    }
    
    for (key,value) in dic_value{
        if k <= value{
            stop_list.append(key)
        }
    }
    
    for (key, value) in dic_report{
        for j in value{
            if stop_list.contains(j){
                dic_result[key]! += 1
            }
        }
    }
    
    for i in id_list{
        result.append(dic_result[i]!)
    }
    
    return result
}

그래서 방식을 수정했다.
기존에 [신고한 사람 : [신고 대상자]]형식으로 했던 것을
[신고 당한 사람 : [신고 한 사람]]으로 수정했다. 그제서야 시간이 줄어들었다.

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var dic_report : [String : [String]] = [:] 
    var dic_value : [String : Int] = [:]
    var dic_result : [String : Int] = [:]
    var result : [Int] = []
    
    for i in id_list{
        dic_report[i] = []
        dic_value[i] = 0
    }
    
    for i in report
    {
        let report_array = i.split(separator:" ").compactMap{ String($0) }
        
        if !dic_report[report_array[1]]!.contains(report_array[0]) {
            dic_report[report_array[1]]!.append(report_array[0])
        }
    }

    for (key, value) in dic_report{
        if k <= value.count{
            for i in value{
                dic_value[i]! += 1
            }
        }
    }
    
    for i in id_list{
        result.append(dic_value[i]!)
    }
    

    
    return result
}