[알고리즘 문제 - 프로그래머스] - 압축

<입출력 예시>

<풀이>

우선 사전의 역할을 하는 리스트를 만들어야 겠다는 생각을 했습니다.

 

리스트에는 문제에서 제시해준것처럼 알파벳 대문자 A부터 Z까지 넣었습니다.

 

저는 리스트를 썼는데 이 부분은 딕셔너리를 써도 무방하다고 생각합니다.

 

여기서 input으로 들어오는 메시지를 리스트로 바꿔 넣었습니다.

 

이거는 pop을 써서 앞에서부터 하나씩 제거해나가기 위함인데요. 

 

string은 pop function을 지원하지 않기 때문에 그랬습니다.

 

다른 방법으로는 slice를 써서 string을 압축하려는 만큼씩 계속 자르는 방법도 있겠네요.

 

 

<코드>

def solution(msg):
    answer = []
    dictionary = [chr(i) for i in range(65,91)]
    msg_lst = [ch for ch in msg]
    comp = ""
    index = 0
    
    while msg_lst:
        comp += msg_lst[0]
        if comp in dictionary:
            index = dictionary.index(comp) + 1
            msg_lst.pop(0)
        else:
            answer.append(index)
            dictionary.append(comp)
            comp = ""
    
    answer.append(index)
    return answer

먼저 메시지 리스트에서 가장 첫번째 문자가 사전 안에 있는 확인 합니다.

 

만약 사전 안에 있다면 이미 사전에 입력 되어 있는 문자임으로 pop을 이용해서 메시지 리스트에서 빼냅니다.

 

사전에서 문자의 인덱스를 variable을 통해서 따로 저장해둡니다.

 

이렇게 해서 사전에 없는 문자열을 발견하면 else 문으로 들어가서

 

이전에 저장해둔 인덱스를 나중에 아웃풋으로 리턴하기 위해 answer에 저장해둡니다.

 

그리고 사전에 없는 문자열을 사전에 등록해줍니다.

 

이 알고리즘의 결과는....

 

 

정확성 테스트만 있고 효율성 테스트는 따로 없네요.

 

사실 코드를 짜면서도 효율성 테스트 있을꺼라는 예상을 하면서 

 

나름대로(?) 효율성을 고려하고 짠 코드라서 그런가

 

정확성 테스트를 통과하는데는 시간적인 문제가 전혀 없었습니다.

 

알고리즘을 짜면서 걸릴만한 edge case 딱히 떠오르진 않았는데

 

역시 아무 문제 없었네요.

 

알고리즘 문제를 풀면서 생각해낸 코드가 한번에 통과가 될때는 참 기분이 좋네요