문제 분석
요약 | 이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하여라.
Input data :
- id_list:
Array<String>- 2 ≤ id_list의 길이 ≤ 1,000
- 1 ≤ id_list의 원소 길이 ≤ 10
- id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
- id_list에는 같은 아이디가 중복해서 들어있지 않습니다.
- report:
Array<String>- 1 ≤ report의 길이 ≤ 200,000
- 3 ≤ report의 원소 길이 ≤ 21
- report의 원소는 "이용자id 신고한id"형태의 문자열입니다.
- 자기 자신을 신고하는 경우는 없습니다.
- 1 ≤ k ≤ 200, k는 자연수입니다.
- return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.
report의 길이가 20만으로 상당히 길다. 이부분을 유의해야 한다.
Output data :
IntArray
풀이
전개 순서
- 동일 유저 신고 횟수가 중복되지 않도록 set으로 변환(repoToSet)
- 신고 내역을 순회하면서
- 피신고 유저의 피신고 횟수 누적하여 저장(reportCount)
- 저장된 reportCount에서 정지 대상 유저만 필터링(.filterValues { it >= k })
- 정지 대상 유저 ID(reported)만 가져와서
- 신고 내역 중 reported 값이 스페이스 뒤에 있는 데이터만 필터링. 즉, 해당 피신고자를 신고한 유저 7. 데이터만 필터링
- 필터링된 데이터에서 신고한 유저의 아이디를 찾아서(map { it.split(" ")[0] })
- 해당 유저가 정지시킨 횟수를 누적
- 정지시킨 횟수가 저장되어 있는 목록에 유저 목록이 있으면 해당 값만 배열에 저장하여 리턴
사용한 data type
MutableMap
신고 당한 유저와 정지 이메일을 받게 될 유저의 목록을 <String, Int> 쌍의 Map으로 관리하였다.
Set
한 명의 유저가 여러번 동일 유저를 신고할 수는 없으므로 중복 데이터는 Set으로 변환하여 제거하였다.
(이걸 toList.distinct()로 처리하는 사람들도 있었는데, 이 정도 크기의 데이터를 다룰 때 속도 차이가 크지는 않은 것 같다)
코드
class Solution { fun solution(id_list: Array<String>, report: Array<String>, k: Int): IntArray { val reportCount = mutableMapOf<String, Int>().withDefault { 0 } val suspendedCount = mutableMapOf<String, Int>().withDefault { 0 } var repoToSet = report.toSet() //신고당한 유저 누적 횟수 저장 repoToSet.forEach { reportCount[it.split(" ")[1]] = reportCount.getValue(it.split(" ")[1]) + 1 } //정지 대상 유저 필터링 및 신고자가 정지시킨 유저 수 저장 reportCount.filterValues { it >= k }.forEach { (reported, _) -> repoToSet.filter { it.endsWith(" $reported") }.map { it.split(" ")[0] } .forEach { suspendedCount[it] = suspendedCount.getValue(it) + 1 } } return id_list.map { suspendedCount.getValue(it) }.toIntArray() } }
삽질 기록
처음에는 코드를 이렇게 작성했었다.
class Solution {
fun solution(id_list: Array<String>, report: Array<String>, k: Int): IntArray {
var answer: IntArray = intArrayOf()
var reportedId = mutableListOf<MutableSet<String>>() //전체 id별 신고한 id 목록
var reportCount = hashMapOf<String, Int>().apply { id_list.forEach { put(it, 0) } } //id별 신고당한 횟수 누적
var suspendedCount = mutableMapOf<String, Int>().apply { id_list.forEach { put(it, 0) } } //id별 정지 시킨 이용자 수 누적
//report의 중복 제거
var repoToSet = report.toList().distinct()
//id별 신고 횟수 정리
id_list.forEach { id ->
var repoPerId = mutableSetOf<String>() //특정 id가 신고한 id 목록
repoPerId.add(id)
repoToSet.forEach { repo ->
val splitRepo = repo.split(" ")
if (id == splitRepo.first()) {
repoPerId.add(splitRepo.last()) //특정 id가 신고한 id 목록에 적립
reportCount[splitRepo.last()] = reportCount[splitRepo.last()]!! + 1 //신고당한 id 적립
}
}
reportedId.add(repoPerId) //특정 id의 신고 내용을 전체 목록에 적립
}
//정지 id 처리
reportCount.forEach { (key, value) ->
if (value >= k) {
reportedId.forEach { id ->
if (id.contains(key)) {
if (id.first() != key) {
suspendedCount[id.first()] = suspendedCount[id.first()]!! + 1
}
}
}
}
}
suspendedCount.forEach {
answer += it.value
}
return answer
}
}- 답은 구하지만, 시간초과되는 케이스가 2개 있어서 fail을 받았었다.
- 문제는 id_list.forEach 안에 repoToSet.forEach를 하나 더 두었던 것이다.
- 이렇게 되면 저 이중 for문 안에서 유저 목록(1,000) * 신고 목록(200,000) = 200,000,000 번이나 연산을 해야했다..
- 심지어 이미 위에서 중복 데이터를 처리하느라 신고 목록을 한 번 순회했었기 때문에 더욱 시간이 많이 필요했다.
그래서 코드를 많~이 수정해서.. 최종적으로 pass는 받았지만.. 하도 서치를 많이해서 푼거라 온전히 내 힘으로 풀었다고 보기에는 어려울 것 같다.
최근 자료 구조 공부를 다시하면서 내가 어떤 타입의 데이터를 사용해야할지는 점점 감이 오는 것 같다.
문제는 로직을 짜는 것인데... 많은 데이터 안에서 또 다른 많은 데이터를 조회하는 식의 방식이 좋지 않다는 것은 이번 케이스로 잘 느꼈다. 다만 다음에 또 이런 문제를 마주했을 때에 내 힘만으로 제대로 풀 수 있는지는 아직 모르겠다.
문제는 로직이다..
[TIL-240329]
