[프로그래머스]압축

문제 설명

구현 문제. 문제를 잘 읽고 이해해서 말하는 대로 구현하라.

예제도 매우 잘 나와있어서 정말 잘 읽어보고 알고리즘을 작성하면 된다.

읽은 내용 바탕으로 설명하자면,

1.

K A K A O
↑

• K문자는 사전에 있으므로 다음 A로 넘어간다

2.

K A K A O
  ↑

• KA는 사전에 없다. 따라서 KA를 사전에 등록하고 K의 인덱스 번호를 출력.

3.

K A K A O
  ↑

• A부터 다시 시작. A는 사전에 있으므로 다음 K로 넘어간다. (1~2과정 반복)

4.

K A K A O
    ↑

• AK는 사전에 없으므로 사전 등록, A의 인덱스 번호를 출력한다.

5.

K A K A O
    ↑

• K는 사전에 있으므로 다음 A로 이동

6.

K A K A O
      ↑

• 2.에 의해 KA또한 사전에 있다. 다음 O로 넘어간다

7.

K A K A O
        ↑

• KAO는 사전에 없다. 따라서 KA의 인덱스 번호를 출력한다. O부터 다시 시작.

8.

K A K A O
        ↑

• O는 사전에 있다. 인덱스번호 출력 후 종료.

문제 접근

1. msg token을 확인한다. i = 0 초기화.

2. 확인한 문자를 담아줄 letter를 선언한다.

3. 현재 i위치부터 letter가 사전에 없을 때까지 반복한다. i += 1

4. 사전에 letter를 등록해준다. 이때 maxIdx 고려.

5. letter의 마지막 전까지는 사전에 있는 단어이므로 해당 인덱스를 출력한다.

6. 2~4 과정을 idx가 msg의 길이 이내일 때까지 반복.

위 과정을 이와같이 작성하면 되리라 봤다.

구현

방법1

dict = {}
for i in range(65,65+26):
    dict[str(chr(i))] = i-65+1

def solution(msg):
    answer = []
    i = 0
    maxIdx = 26
    msgLength = len(msg)
    while i<msgLength:
        letter = msg[i]
        while letter in dict:
            i += 1
            if i>=msgLength: #인덱스
                break
            letter+=msg[i]

        if i != msgLength:
            maxIdx += 1
            dict[letter] = maxIdx
        if i != msgLength:
            answer.append(dict[letter[:-1]])
        else:
            answer.append(dict[letter])


    return answer

문제 접근 방법처럼 구현하면 문제가 생겼다.

 while letter in dict:
            i += 1
            if i>=msgLength: #인덱스
                break
            letter+=msg[i]

이 부분에서 letter가 사전에 있을 때까지 letter에 문자를 넣어준다고 반복문 조건을 달았지만 index가 벗어나도 반복문을 나와야하기 때문이다.

따라서 while문을 빠져나온 letter는 3가지 경우를 지닌다.

1. index를 벗어나지 않고, 내 의도대로 letter가 사전에 없는 단어인 경우
2. index를 벗어나와서 letter가 내 의도대로 사전에 없는 단어인 경우
3. letter가 사전에 있는 단어지만, index때문에 벗어나온 경우.

3번 때문에 결국 while문을 빠져나왔을 때 index와 msg의 길이를 고려하여 경우 letter 인덱스를 출력해줘야하는 코드를 작성해야 한다.

논리 전개가 매끄럽지 못하다. 그렇다고 위 while문에서 index를 벗어나는 경우를 고려하지 않으면 안된다.

그래서 반드시! 마지막에 사전에 없는 단어가 나오도록 하기 위해 대안으로 msg에 '#'이라는 특수문자를 더하였다.

그런데 이렇게 코드를 작성하면 추후에 letter가 특수문자도 허용할 경우 에러가 발생할 수 있다. 기대에 맞지 않는 알고리즘이라 볼 수 있겠지만 일단 문제는 풀어야 하니까 ㅎㅎ; 그래서 아래처럼 작성하면 전개는 좀 더 깔끔해진다.

방법2

dict = {}
for i in range(65,65+26):
    dict[chr(i)] = i-65+1

def solution(msg):
    msg+="#"
    answer = []
    i = 0
    maxIdx = 26
    msgLength = len(msg)
    while msg[i] != '#':
        letter = msg[i]
        while letter in dict:
            i += 1
            if i>=msgLength:
                break
            letter+=msg[i]

        maxIdx += 1
        dict[letter] = maxIdx
        answer.append(dict[letter[:-1]])

    return answer

Depth 줄이기.

한편, depth를 1개 늘렸기 때문에 발생한 복잡성이 존재한다.

• index벗어날 때까지 확인할건데,
  • 문자 봤을 때 사전에 있는 문자가 있으면 index를 1 늘려줘.

첫번째 while문에서 index를 벗어날 때까지 반복한다고 했으면 while문에서 index를 증가시켜줘야할 것 같은데 사실상 문자를 하나씩 보는 단계에서 늘려주게 된다.

문자하나씩 계속 진행해보면서 있으면 letter에 추가하고 넘어간다.
없다면,letter을 사전에 집어넣은다음 letter을 현재위치의 문자(msg[i])로 초기화 시키면 되는 일 아닌가?

그리고 하나씩 진행하면서 봤기 때문에 마지막 문자는 사전에 존재하는 단어인지 모른다.

따라서 letter가 사전에 없는 단어인지 확인 후 넣어주면 논리적으로 깔끔해지기도 한다.

그래서 구현하면 아래와 같다.

(단어가 사전에 없는 경우 추가시켜준다음 for문을 빠져나왔다. 따라서 마지막에 추가한 단어가 letter의 문자라면 letter는 위에서 말한 단어가 사전에 없는 경우에 해당한다.)

방법3

dict = {}
for i in range(65,65+26):
    dict[chr(i)] = i-65+1

def solution(msg):
    answer = []
    maxIdx = 26
    msgLength = len(msg)
    letter = ''

    for i in range(msgLength):
        letter += msg[i]
        if letter not in dict:
            maxIdx += 1
            dict[letter] = maxIdx

            answer.append(dict[letter[:-1]])
            letter = msg[i]

    #사전에 있던 단어이면 인덱스를 출력하라.
    if dict[letter] != maxIdx:
        answer.append(dict[letter])

    return answer

정리

흠... 인덱스가 종료될 때가 항상 문제가 된다. 위에서 본 사례처럼

특정 조건을 만족할 때마다 인덱스를 증가시키는 경우.

인덱스때문에 특정 조건을 만족시키지 못할 수 있으므로 위와 같은 케이스를 매 고려하자.

방법을 일반화하여 말하자면 이렇다.

1. index가 넘어가서 빠져나오지만, 항상 특정 조건을 만족하고 반복문을 빠져나오도록 특정 조건과 반대되는 값을 마지막에 넣어라.
2. 1.을 적용하지 못한다면, 마지막에 특정 조건을 만족했는지 재확인하라.