Algorithm / 신고 결과 받기

문제

프로그래머스 / 신고 결과 받기

1) 문제 풀이

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var reportUsers: [String:[String]] = [:]
    var reportedUsers: [String: Int] = [:]
    var duplicationReports: Set<String> = []
    var badUsers: [String] = []
    var answer = [Int](repeating: 0, count: id_list.count)
    
    for i in report where !duplicationReports.contains(i) {
        duplicationReports.insert(i) // 중복 방지
        let users = i.split(separator: " ").map { String($0) }
        
        reportUsers[users[0], default: []].append(users[1])
        reportedUsers[users[1], default: 0] += 1
    }
    
    for j in reportedUsers {
        if j.value >= k {
            badUsers.append(j.key)
        } else {
            continue
        }
    }
    
    for user in badUsers {
        for x in reportUsers where x.value.contains(user) {
            let index = id_list.firstIndex(of: x.key)!
            answer[index] += 1
        }
    }
    
    return answer
}

결과

2) 코드 개선

❌ 문제점 분석

• 중복된 신고 처리 방식이 비효율적

  • 신고가 "A B" 형식으로 들어오기 때문에 Set<String>으로 처리하고 있지만, 추후 가공을 위해 분해해야 하므로, Set<(신고자, 피신고자)> 형식이 더욱 직관적

• badUsers를 배열로 보관하고 이중루프 사용

  • 이중 루프에서 .contains 사용 = O(n^2) 수준의 시간복잡도, 비효율적
  • 특히 reportUsers 값 배열에 대해 .contains 검색이 느림

✅ 개선 포인트

• Set<(신고자, 피신고자)>를 사용해 중복 신고를 명확히 제거

• Dictionary<String, Set<String>>로 reportUsers 구조 개선

• badUsers도 Set<String>으로 바꾸어 탐색 최적화

• id_list를 빠르게 인덱싱하기 위해 [String: Int] 매핑 사용

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    // 신고자별 신고 대상 저장 (중복 제거)
    var reportUsers: [String: Set<String>] = [:]
    // 피신고자별 신고당한 횟수
    var reportedCount: [String: Int] = [:]
    // 결과 저장
    var answer = [Int](repeating: 0, count: id_list.count)
    // 사용자 인덱스 빠르게 찾기 위한 맵
    let userIndex = Dictionary(uniqueKeysWithValues: id_list.enumerated().map { ($1, $0) })

    // 1. 중복 제거한 신고 처리
    let uniqueReports = Set(report)
    for entry in uniqueReports {
        let parts = entry.split(separator: " ").map { String($0) }
        let reporter = parts[0], reported = parts[1]
        
        reportUsers[reporter, default: []].insert(reported)
        reportedCount[reported, default: 0] += 1
    }

    // 2. 정지 대상 사용자 찾기
    let suspendedUsers = Set(reportedCount.filter { $0.value >= k }.map { $0.key })

    // 3. 각 사용자 별 메일 받은 횟수 카운트
    for (reporter, reportedSet) in reportUsers {
        let mailCount = reportedSet.filter { suspendedUsers.contains($0) }.count
        if let idx = userIndex[reporter] {
            answer[idx] = mailCount
        }
    }

    return answer
}

결과