신고 결과 받기

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

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

 

---

내 풀이

 

처음 풀이  (6개 정도 시간 초과)

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    var accumulatedNumberOfReport = [String: Int]()
    for eachID in id_list {
        accumulatedNumberOfReport[eachID] = 0
    }

    let removedDuplicatesArray = Array(Set(report)).map({$0.split(separator: " ")})


    removedDuplicatesArray.forEach({
        accumulatedNumberOfReport[String($0[1])]! += 1
    })

    let suspendedUser: [String] = accumulatedNumberOfReport.filter({$0.value >= k}).map({$0.key})

    let reportedUserArray: [String.SubSequence] = removedDuplicatesArray.filter({suspendedUser.contains(String($0[1]))}).map({$0[0]})

    return id_list.map{(eachID) in reportedUserArray.filter({eachID == $0}).count}
}

1. [유저 아이디: 누적 신고당한 횟수] 형식의 Dictionary를 생성하고, 각 아이디의 Value에 0을 넣는다.
2. Set을 사용하여 신고 내용이 저장된 배열의 중복 값을 제거한다.
3. 중복 값이 제거된 배열을 순환하면서 Dictionary의 Value에 신고당한 횟수를 입력한다.
4. k와 비교했을 때 누적 신고 횟수가 더 많은 유저들을 배열로 저장한다. (이용 정지 유저들)
5. 중복값이 제거된 배열에서 이용 정지 유저를 신고한 유저들을 배열로 저장한다.
6. 5에서 저장한 배열을 이용하여 각 유저가 정지시킨(?) 유저의 수를 반환한다.

 

 

수정 1  (2개 시간 초과)

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    // 각 아이디 별로 누적 신고횟수를 저장하는 Dictionary생성
    var accumulatedNumberOfReport = [String: Int]()
    for eachID in id_list {
        accumulatedNumberOfReport[eachID] = 0
    }

    // 중복값이 제거된 신고 리스트
    let removedDuplicatesArray: [[String.SubSequence]] = Set(report).map({$0.split(separator: " ")})

    // 신고 리스트를 순환하면서 신고당한 유저를 count += 1 올림
    removedDuplicatesArray.forEach({
            accumulatedNumberOfReport[String($0[1])]! += 1
    })

    // id_list에 filter를 사용하여 누적 신고횟수가 k를 넘는 유저만 가져옴
    let suspendedUser: Set<String> = Set(id_list.filter({accumulatedNumberOfReport[$0]! >= k}))

    // 신고 리스트의 [1] 즉, 신고당한 유저가 이용정지 되었는지 확인하여 이용정지된 유저를 신고한 유저들의 이름을 담은 Array 생성
    let reportedUsers = removedDuplicatesArray.filter({
        suspendedUser.contains(String($0[1]))
    }).map({$0[0]})

    // 정지 유저를 신고한 유저의 리스트를 바탕으로 각 유저가 몇번 신고했는지 count해서 Array로 반환
    return id_list.map{(eachID) in reportedUsers.filter({eachID == $0}).count}
}

신고당한 유저가 정지되었는지 확인하는 과정에서 사용한 contains() 메서드를

Array가 아닌 Set에서 동작하도록 수정  (Set type에서 contains()를 사용하면 O(1))

 

 

 

수정 2 (성공)

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    // 각 아이디 별로 누적 신고횟수를 저장하는 Dictionary생성
    var accumulatedNumberOfReport = [String: Int]()

    // 중복값이 제거된 신고 리스트
    let removedDuplicatesArray: [[String.SubSequence]] = Set(report).map({$0.split(separator: " ")})

    // 신고 리스트를 순환하면서 신고당한 유저를 count += 1 올림
    removedDuplicatesArray.forEach({
            accumulatedNumberOfReport[String($0[1]), default: 0] += 1
    })

    // id_list에 filter를 사용하여 누적 신고횟수가 k를 넘는 유저만 가져옴
    let suspendedUser: Set<String> = Set(id_list.filter({accumulatedNumberOfReport[$0, default: 0] >= k}))

    // 신고 리스트의 [1] 즉, 신고당한 유저가 이용정지 되었는지 확인하여 이용정지된 유저를 신고한 유저들의 이름을 담은 Array 생성
    let reportedUsers = removedDuplicatesArray.filter({
        suspendedUser.contains(String($0[1]))
    }).map({$0[0]})

    // [유저 아이디 : 신고한 횟수] 형식의 Dictionary 생성
    var reportCount: [String: Int] = [String: Int]()
    for eachUser in reportedUsers {
        reportCount[String(eachUser), default: 0] += 1
    }

    // userID를 사용하여 [유저 아이디 : 신고한 횟수]Dictionary의 value값을 배열로 반환
    return id_list.map({reportCount[$0] ?? 0})
}

1. dictionary에 초기 value인 0을 입력하는 과정 생략 ( dictionary[key, default: _] += 1
2. [유저 아이디: 신고한 횟수] 형태의 dictionary를 생성하여 각 아이디 별로 신고로 정지시킨 유저의 수를 저장
3. 각 유저 아이디를 key로 사용하여 (2)에서 생성한 Dictionary의 value를 배열로 변환하여 리턴

 

 

 

contains() 메서드를 사용해야 할 때 해당 type을 Set으로 구현해도 문제가 없는지 잘 생각해보자!

 

이 문제는 해시 테이블을 활용할 줄 아는지 묻는 문제였는데

코드를 짧게 작성하고 싶은 이상한 병이 생겨서 고차 함수를 남발하다가 시간 초과가 나온 것 같다.

 

문제를 풀 때 해시 테이블을 사용하여 시간 복잡도를 줄일 수 있을지 한번 더 고민해보고 문제에 접근해야겠다.!