강의로 돌아가기
andyscoffee

몇몇 테스트 케이스에 시간 초과 판정을 받는데 포문을 줄일 방법이 있을까요?

이중 포문을 두 번이나 사용하다 보니 시간 초과 판정을 받는 것 같습니다

돌리거나 코드를 조금씩 수정할 때마다 다르긴 한데 1~4개 정도의 테스트 케이스는 시간 초과 판정이 나오더라고요

어떻게 잘 생각하면 한 번 돌릴 때 answer까지 해결해 하나로 합치거나 다른 방법으로 줄일 수 있을 것 같은데 초보라 좀 어렵네요

혹시 방법이나 힌트를 주실 수 있으신 분 계신가요?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def solution(id_list, report, k):
    check_list = set()  # 제재가 확정된 사람을 저장할 집합(중복 아이디 없기에 집합 활용)
    answer = [0] * (len(id_list))

    dic = {}
    rp_num = {}  # id별 신고당한 횟수 저장용 사전

    for i in id_list:
        dic[i] = []  # 신고자 : [신고당한목록] 사전 생성을 위한 key: 빈 리스트 생성
        rp_num[i] = 0

    for i in range(len(report)):
        singo, hogu = report[i].split()  # 분리
        if hogu not in dic[singo]:  # 중복신고가 아니라면
            dic[singo].append(hogu)  #사전에 삽입


    for id in range(len(id_list)):  # 유저 목록만큼 반복
        for data in list(dic.values()):  # 중복을 제거한 레포트를 순회하면서
            if id_list[id] in data:
                rp_num[id_list[id]] += 1  # 유저별 신고당한 횟수 체크
                if rp_num[id_list[id]] >= k:
                # 신고당한 횟수가 k회를 넘는다면
                    check_list.add(id_list[id])  # 정지 확정 집합에 삽입

    for reported in check_list:
        for j in range(len(id_list)):
            if reported in list(dic.values())[j]:
                answer[j] += 1
    return answer
1 개의 답변
전현서

일단 딕셔너리의 특성을 거의 살리지 못하고 거의 이중 for문으로 사용하는 것 같습니다.
딕셔너리의 O(1)의 시간복잡도를 최대한 사용하지 못했군요..

간단한 알고리즘을 살펴봅시다.
중복제거는 report 배열에만 해주면 됩니다.
왜냐하면 한 사람은 어떤 사람을 한 번밖에 신고할 수 있습니다.
즉, muzi가 prodo를 두 번 신고하는 경우는 존재하지는 않겠죠.
근데 잘생각해보면 한 사람은 한 번에 한 명만 신고가 가능합니다.
근데 두 번 신고하는 경우를 배열로 준다는 거는 같은 원소가 두 번 들어있는 걸 하나로 퉁치라는 의미와도 같습니다.
즉 중복제거는 report배열의 원소들이 유일한 값을 가지도록 하면 됩니다. 그럼 muzi가 prodo를 신고한다는 내용이 두 번 있으나,
세 번 있으나 하나로 처리가 될 겁니다.

딕셔너리를 이용하여 신고 당한 사람이 누구이며, 몇 번 신고 당했는지를 카운트 합니다.
즉 report 문자열을 split()하였을 때, 뒤에 오는 값이 될겁니다.
그 값을 가지고, 먼저 report를 순회하면서, 딕셔너리에 어떤 사람이 몇 번 신고당함.
이런 식으로 파악을 한 번 해줍니다.

다음, 신고당한사람과 그 횟수가 저장된 딕셔너리를 통해 k이상 신고당한 사람들의 딕셔너리를 추가 생성합니다.
즉 딕셔너리를 순회하여 k번 이상인 사람만 다시 새로운 딕셔너리에 저장합니다. 이 때는 이미 저장된 id자체가 k번 이상인 사람들만
존재하므로 따로 값은 중요하지 않고 key값만 확인 하는 용도가 됩니다.
기존 딕셔너리에서 k번 미만을 제거 하지 않고 새로 만드는 이유는, 새로 만드는게 정신건강에 이롭기 때문입니다.(파이썬 언어 특성상 짜증납니다)

또 다른 딕셔너리를 만들어서, 어떤 사람이 어떤 사람을 신고했는지에 대한 정보를 모아봅시다.
report를 순회하면서 공백기준으로 왼쪽에 있는 값이 key가 됩니다. 오른쪽에 있는 값이 value가 됩니다.
value가 아까 새로만든 k번 이상 신고당한 사람 리스트에 존재한다면 해당 딕셔너리에
신고자 : 횟수 와 같이 저장합니다. key값이 없다면 key를 새로 만들어서 1을 넣어주고, key값이 있다면 기존 value에 +1을 해줍니다.

마지막으로 id_list를 돌면서, 해당아이디를 딕셔너리에서 가져와서,
그 값을 그대로 정답에 순서대로 추가시켜주면, 답을 반환할 수 있습니다.

  • andyscoffee

    조금 늦게 확인해서 죄송합니다 상세한 답변 감사드립니다!

    andyscoffee―2022.01.20 21:09
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.