[Programmers] [3차] 압축

문제 바로가기 : https://programmers.co.kr/learn/courses/30/lessons/17684
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

길이가 최대 1000이므로 맵으로 상당히 쉽게 해결할 수 있다.
일단 제일 작은 단위인 1글자는 A~Z가 들어오고 각각 1~26의 색인 번호가 할당 돼있으므로 등록해준다.

for(int i=0; i<26; i++){
    string s = ""; s += 'A'+i;
    m[s] = i+1;
}

그 다음엔 사전에 있는 경우를 체크하는 exist()를 통해서 해결한다. 자료형은 pair<int, int>로 했다.

1. 존재하는 문자열이면 다음 문자를 추가한다.
   
2. 중간에 존재하지 않는 문자열을 만나면 사전에 등록한다.
   
3. 현재 문자열이 존재하지 않는다는건 마지막 문자를 제외한 문자열은 사전에 존재함을 의미한다.
   따라서 직전 인덱스와 해당되는 문자열을 반환한다.
4. for문을 끝까지 통과했다면 전달받은 인덱스부터 마지막 인덱스까지의 문자열이 사전에 있음을 의미한다.