[알고리즘] 프로그래머스 오픈채팅방 - 시간 초과 해결

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42888?language=python3 

코딩테스트 연습 - 오픈채팅방

 

---

시간초과된 sourceCode:

def solution(record):
    def change_nickname(id, nickname):
        try:
            index=id_arr.index(id)
            nickname_arr[index] = nickname
        except:
            return None
        
        
    def find_nickname(id):
        index=id_arr.index(id)
        return nickname_arr[index]
        
    
    answer = []
    admin = []
    id_arr = [0 for i in range(100001)]
    nickname_arr = [0 for i in range(100001)]
    result = [[0 for i in range(2)] for i in range(100001)]
    num = -1
    for r in record:
        user = r.split()
        
        if user[0]=='Enter':
            # 처음 들어온 유저
            if change_nickname(user[1],user[2]) == None:      
                num+=1
                result[num] = ["E",user[1]]
                id_arr[num] = user[1]
                nickname_arr[num] = user[2]
        
        elif user[0] == 'Leave':
            num+=1
            result[num] = ["L",user[1]]
        
        else:  # Change
            if len(user[2]) >=1 and len(user[2]) <=10:
                change_nickname(user[1],user[2])
            
    
    for r in result:
        print(r)
        if r[0]==0:
            break
            
        nickname = find_nickname(r[1])
        if r[0]=="E":
            answer.append(str(nickname)+"님이 들어왔습니다.")
        else:
            answer.append(str(nickname)+"님이 나갔습니다.")     
    
    return answer

 

이렇게 코드를 짰더니 시간초과가 발생했다.

index()를 하면서 시간이 절약될 것이라고 생각했는데 인덱스의 모든 요소를 검사하기 때문에 시간이 오래걸렸던 것이다.

그리고 이 문제에서는 id로 nickname을 찾는 것이기 때문에 딕셔너리 자료형을 써서 시간을 훨씬 절약할 수 있었다.

딕셔너리 자료형은 모든 요소를 순차적으로 검색하는 것이 아니라 key값만 딱! 보기 때문에 시간이 짧게 걸린다.

---

다음은 딕셔너리 자료형을 사용해서 시간 초과를 해결한 답이다!

 

- 시간초과 해결 SourceCode

def solution(record):
    
    answer = []
    result = {} # 딕셔너리 
    
    for r in record:
        user = r.split()
        
        if user[0]=='Enter' or user[0]=='Change':
            result[user[1]] = user[2]
    
    for r in record:
        user = r.split()
        
        if user[0] =="Enter":
            answer.append(result[user[1]]+"님이 들어왔습니다.")
        elif user[0]=="Leave":
            answer.append(result[user[1]]+"님이 나갔습니다.")     
    
    return answer