[Swift 알고리즘] Programmers 신고 결과 받기

× △

Level 1 2022 KAKAO BLIND RECRUITMENT 

신고 결과 받기

문제 설명
이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ id_list 의 길이 ≤ 1,000
- 1 ≤ report 의 길이 ≤ 200,000
- 1 ≤ k ≤ 200, k는 자연수입니다.
- return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

크.. 역시 카카오인가.. 레벨 1인데도 쉽지 않다.. 

 

입출력 예시

print(solution(["con", "ryan"],["ryan con", "ryan con", "ryan con", "ryan con"],3)) //[0,0]
print(solution(["muzi", "frodo", "apeach", "neo"],["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"],2)) //[2,1,1,0]

1차 시도 : 87.5점 시간초과

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    let report = Set(report) //1 중복 제거
    var reportDict = [String:[String]]()
    var mailedUsers = [String]()
    var result = [Int]()
    //2 딕셔너리 초기화 선언
    for i in id_list {
        reportDict.updateValue([], forKey: i)
    }
    //3 딕셔너리로 신고자 목록 생성 - 신고당한 유저 : [신고자 목록] 
    for i in report {
        let reporter = String(i.split(separator: " ")[0])
        let reported = String(i.split(separator: " ")[1])
        reportDict[reported]?.append(reporter)
    }
    //4 메일 수신 신고자 배열 생성
    for (key, value) in reportDict {
        if value.count >= k {
            mailedUsers.append(contentsOf: value)
        }
    }
    //5 사용자 순서별 메일 수신 횟수 배열 생성
    for i in id_list {
        result.append(mailedUsers.filter{ $0 == i }.count)
    }
    
    return result
}

2번으로 딕셔너리를 초기화시켜놓고 시작했는데 굳이 반복문 들여 할 필요 없이 3번 안에서 분기처리 해주는게 나을듯

4번에서 메일 수신한 신고자들 목록을 배열에다 넣고, 5번에서 반복문 안에 필터 써서 계산해줬는데 시간이 너무 오래 걸린 것 같다. 

 

2차 시도 : 100점 통과

1. set - report 중복제거

2. 신고자 목록 dict - 신고받은 사람 : [신고한 사람들]

3. 신고한 사용자 dict - 신고한 사람 : 메일 수신횟수

4. result 배열 생성

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    let report = Set(report) //1. 중복 제거
    var reportDict = [String:[String]]()
    var mailDict = [String:Int]()
    var result = [Int]()
    //2. 신고자 목록 dict - 신고받은 사람 : [신고한 사람들]
    for i in report {
        let reporter = String(i.split(separator: " ")[0])
        let reported = String(i.split(separator: " ")[1])
        if reportDict[reported] != nil {
            reportDict[reported]?.append(reporter)
        } else {
            reportDict.updateValue([reporter], forKey: reported)
        }
    }
    //3. 신고한 사용자 dict - 신고한 사람 : 메일 수신횟수
    for (key, value) in reportDict {
        if value.count >= k {
            for i in value {
                if mailDict[i] != nil {
                    mailDict[i]! += 1
                } else {
                    mailDict.updateValue(1, forKey: i)
                }
            }
        }
    }
    //4. 답안 배열 생성 
    for i in id_list {
        result.append(mailDict[i] ?? 0)
    }
    return result
}

Java 풀이 강의를 들었는데, 해시맵을 사용해서 푸는 문제라고 하더라.

Swift에서는 딕셔너리 사용해서 편하게 풀 수 있는 것 같다!

getOrDefault도 그냥 ?? 사용해서 default 값 설정해주면 됨. 

 

 

 

참고 : youtube - 개발자로 취직하기

---

10개월 전에는 문제를 아무리 읽어봐도 어떻게 풀어야 할 지 감이 오지 않고, 답을 봐도 도무지 이해가 안가던 문제였는데

10개월이 지난 지금 그 문제를 다시 들고앉아 푸는데 성공했다!

비록 첫번째 시도에서는 3문제가 시간초과 떴지만 그래도 그게 어디야ㅠㅠ 

뿌듯하고 신기하다. 내가 발전이 없진 않았구나 하며 조금은 위안이 된다. 

(1월의 나는 딕셔너리 사용이 많이 미숙했나봄..)

 

2022-01-10

 

실패 답안

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    if (id_list.count < k) || (report.count < k) {
        return Array(repeating: 0, count: id_list.count)
    }
    var suspended = [String]()
    let arr = Array(Set(report)).map{$0.components(separatedBy: " ")}
    for i in id_list {
        if k <= arr.filter({$0[1] == i}).count {
            suspended.append(i)
        }
    }
    var resultStr = [String]()
    for i in 0...arr.count-1 {
        if suspended.contains(arr[i][1]) {
            resultStr.append(arr[i][0])
        }
    }
    var result = [Int]()
    for i in 0...id_list.count-1 {
        result.append(resultStr.filter{$0 == id_list[i]}.count)
    }
    return result
}

테스트 케이스 3, 9, 11, 14, 15, 20, 21번에서 시간초과로 실패가 떴다..

for문을 너무 많이 사용한거 같긴 한데.. 어떻게 줄이지..?

 

딕셔너리 특성을 사용해서 시간을 줄이는 방법을 강구해 봐야겠다..