[Python/Level.1] 신고 결과 받기 [2022 KAKAO BLIND RECRUITMENT]

문제

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

프로그래머스

풀이

• 중복신고는 처리되지 않으므로 set을 통해 중복을 없애줬다.
  • set은 순서가 없으므로 index를 이용한 값 불러오기가 불가능하다. 따라서 list를 이용해 다시 바꿔줬다.
  • 비효율적이라고 생각한다..
• id_list에 담긴 이름과, 해당하는 인덱스로 처리해주기 위해 딕셔너리를 사용했다. [nidx]
  • 딕셔너리 처리속도가 더 빠르다.
  • 저장공간을 줄일 수 있을까 싶어 {'이름':'인덱스'} 방식으로 저장했다
• 2차원 배열을 생성해, 회원 별 신고한 사람들의 인덱스를 element로 가지는 list들을 요소로 넣었다. [total]
  • split()를 이용해 각 element를 공백 기준으로 나눠주었다 . ["apeach frodo"] --> ['apeach', 'frodo']
    
    • list[0]은 신고자를, list[1]은 신고 당한 사람을 의미한다. 
  • 회원마다 각각의 신고(당한) 공간을 가지고 있다고 가정했다. 안에 들어가는건 신고자 고유 인덱스이다. 
  • 즉, [[2],[2,0],[],[1,0]]  ==> 0번은 2번에 의해, 1번은 0번,2번에 의해 신고됐음을 의미한다. 
• total에 원소로 들어가는 list(total[idx2])의 길이가 k 이상인 경우, 정지 회원 list로 들어간다.
• 정지회원 list 이 완성된 후, 정지될 회원들의 신고공간에서 신고자들의 index를 찾아 해당 값을 +1 시켜준다.

코드

def solution(id_list, report,k):
    nidx={}
    answer=[]
    total=[]
    banID=[]
    
    report = list(set(report)) 
    #집합은 순서가 없어 인덱스를 이용해서 값을 참조할 수 없다.. 따라서 list형으로 다시 전환해줬다.
    for i in range(0,len(id_list)):
        nidx[id_list[i]]= i #{'이름':대응하는 인덱스 번호} ==> 이게 더 찾기 편할것 같아서..
        answer.append(0) #신고 처리된 회원 수 배열 선언: [0,0,0 ... ] 생성
        total.append([]) #2차원 리스트 미리 정의- [[],[],[],[]] (먼저 선언되지 않으면 오류났음)
    
    #신고공간 2차원 배열 채우기
    for l in report:
        report_sp = l.split()
        idx1 = nidx[report_sp[0]] #신고인 고유 인덱스
        idx2 = nidx[report_sp[1]] #피신고인(?) 고유 인덱스
        total[idx2].append(idx1)
        if (len(total[idx2])>=k): #경고 누적 횟수 기준(k) 이상일 경우
            if idx2 not in banID: #새로 갱신된 아이디일 경우 추가 (for 생각 못하고 이걸 추가 안해줘서 오류났었음)
                banID.append(idx2)
    for i in banID:
        for index in total[i]:
            answer[index] +=1 #answer 채우기

    return answer

딕셔너리 형, 2차원 배열을 이용하는 건 생각만 하다가... 복잡할 것 같아서 안했는데

두 가지를 합치니까 훨씬 간단해졌다.

처음엔 시간초과로 틀렸었는데, for문이 많아서 발생한 문제같았다 (case3의 처리시간이 200ms 가까이인걸 보면...)

이래서 최대한 시간 복잡도를 줄이라는 것 같다. 

다른 풀이

• 딕셔너리를 사용하되, {"이름" : 신고당한 횟수}로 구성하고, 1번째 for문을 통해 특정 회원(key)이 신고당한 횟수(value)를 증가시킨다.
  
  • 이때 for ~ in set(report)를 사용했다! index를 이용한 특정 값 꺼내오기는 안되지만 값을 차례대로 하나씩 가져오는 것은 가능한 것 같다!
• 2번째 for문을 통해 신고당한 회원들 중 한도를 넘어가는 회원들을 신고한(!!!) 회원들의 이름을 통해 인덱스를 찾아 (id_list.index()) 해당 값을 증가시켜준다.

이러면 for문을 2번만 사용해 처리 가능하다... 와우

심지어 전체 회원을 대상으로 for문을 돌리는게 아닌, 신고당한 회원에 한해서 진행되므로 시간복잡도가 훨씬 줄어들겠다...

이렇게 되면 banID로 따로 정지 회원 list도 만들 필요가 없어진다. 여러모로 효율적이다.

 

딕셔너리는 이렇게 사용하는 것이군...

+

1.answer을 구성할 때, for문을 돌릴 필요 없이 아래와 같이 이용하면 [0, 0, 0, 0 ...] 이 생성된다.

answer = [0] * len(id_list)

2. for ~ in set(-)도 사용가능하다. set은 특정 값을 꺼내오는게 불가능한 것이다.