카카오 2018 코테 문제2 LZW 압축 문제 (C++)

코딩테스트 연습 - [3차] 압축

카카오 2018 코테에서 나왔던 문제이고, 2번 문제이다. 카카오 사이트 확인해보니, 정답률이 95.8%로 가장 많은 지원자가 푼 문제라고 한다.

 

사담) 저 때 출제된 문제들 중 가장 쉬운 문제..? 나는..푸는데 2시간은 걸렸...

 

 

---

문제를 읽고 코딩 전에 설계한 부분은 다음과 같다.

- 알파벳을 저장할 변수 : 사전형이고 겹치는 일이 없으므로 map 자료구조 사용 (단어, 색인)형태

- 입력받은 string을 저장할 변수 : 한 글자씩 읽어야 하니까 그냥 쉽게 배열 사용

- 정답을 그냥 출력하는게 아니라 [ 1,2,3 ] 이런 형태로 맞춰야하므로 정답 저장용 vector를 사용

- 검색용 string(search)에 추가로 temp라는 임시변수가 필요할 것 같다. 사전에 있다면 다음글자도 읽어줘야하므로.

- while문으로 반복문을 돌리며 검색할건데, 조건은 배열에 담긴 문자열의 끝 '/0' 만날때까지로 하자.

- 읽은 글자가 사전에 있는 경우라면 temp에 현재 상태 저장해두고 search에 다음글자도 읽어서 추가

- 없는 경우 끝내야하므로 이전상태인 temp로 사전에 검색해서 index를 정답 벡터에 저장, temp와 search 초기화

- 마지막에 남은 글자처리를 반복문 바깥에 해줄 것 (ex. kakao면 o가 if문에 걸리고 else에 안들어가므로 answer에 저장되지 않는 문제가 있다) -> 이 작업 때문에 헤맸다(..)

 

 

---

위에서 생각해둔 걸 기반으로 코딩을 해보자.

#include <iostream>
#include <ctype.h>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
map <string, int> dictionary;
map <string, int> :: iterator iter;

0. 필요한 헤더파일

- map, string, vector 자료형 사용하고 편리한 사용을 위해 namespace std추가

- ctype.h는 혹시 input에 소문자 들어오는 경우 대문자로 바꿔주려고 toupper을 임의로 추가해놨다. (영문 대문자만 처리한다고 문제에서 나와있긴 하지만 공부용으로)

- 그 외에 map의 반복자랑 전역변수로 dictionary를 선언해뒀다..

 

 

//dictionary 초기화. 대문자 : 아스키코드 65~90
    for(i=65; i<=90; i++) {
        temp = (char)i;
        dictionary.insert(make_pair(temp, i-64));
    }
    size = dictionary.size();
    temp = "";

1. dictionary 를 초기화하기

- 대문자의 아스키코드가 65~90인데, 이를 (char)형태로 변환하여 temp 변수에다가 넣는다. 이 알파벳들의 인덱스는 1~26이므로 dictionary에 insert할 때 i-64로 인덱스를 넣는다. 

- size 변수는 문자열을 읽으면서 새롭게 만드는 단어들에게 인덱스를 줘야하므로 필요하다. 

- temp변수는 밑에서 사용하므로 꼭 다시 초기화 해줄 것! 

 

    while(input[pos] != '\0') {
        search += toupper(input[pos]); //혹시 input에 소문자 있을 경우 대비 toupper적용. 
        if (dictionary.find(search) != dictionary.end()) {
            temp = search; // 처음에 temp+=search로 실수했는데, 이러면 k가 kka로 중첩되어 버린다. 
            pos++;
        } //search가 사전에 있는 경우
        else {
            iter = dictionary.find(temp);
            answer.push_back((*iter).second); //temp에 있던 단어의 색인
            dictionary.insert(make_pair(search, ++size)); //사전에 추가
            temp = "";
            search="";
        }
    }
    
    //마지막에 if에 걸려서 끝나는 경우까지 answer에 넣어줌.
    iter = dictionary.find(temp);
    answer.push_back((*iter).second);

2. 사전(dictionary) 작업 및 문자열 분석

- 위의 아이디어 부분에서 적어둔 것들을 거의 그대로 가져다 썼다. 

- search += toupper(input[pos]) 로 다음 읽은 글자들까지 search에 저장해둔다. 

저 부분에서 처음에 temp +=  search로 해놨었는데 위에 써둔 주석처럼 중첩된다. 그냥 temp=search하면 되는데 생각이 없었다...

- dictionary.find(temp)를 사용하면 반복자 iterator를 리턴. answer에 넣을때는 인덱스값을 넣어야 하므로 (*iter).second로 넣어야한다. 

- ++size로 넣는 이유는 size가 5라면 다음에 들어갈 단어의 인덱스는 6으로 들어가야 하기 때문

- else문에 걸려서 temp값 answer에 넣었으므로 다시 temp, search초기화 해줄 것.

 

//answer를 배열형태로 출력
    cout<<"[";
    for(i=0; i<answer.size()-1; i++) {
        cout<<answer[i]<<", ";
    }
    cout<<answer[i]<<"]"<<endl;

3. 출력하기

- answer에 들어있는걸 배열 형태로 출력해야 한다. 

- [ 기호 먼저 출력하고 answer.size()-1 까지 반복문을 돌린다. 이유는 맨 마지막 원소 뒤에는 반점이 없어야 하므로. 

- 반복문을 빠져나오고 나서 마지막 원소와 닫는 대괄호 ] 를 출력해주면 된다. 

---

4. 전체 코드

#include <iostream>
#include <ctype.h>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
map <string, int> dictionary;
map <string, int> :: iterator iter;

int main() {
    string search = "", temp = "";
    char input[1001];
    vector <int> answer;
    int i, size, pos = 0;
    cin>>input;

    for(i=65; i<=90; i++) {
        temp = (char)i;
        dictionary.insert(make_pair(temp, i-64));
    }
    size = dictionary.size();
    temp = "";

    while(input[pos] != '\0') {
        search += toupper(input[pos]); 
        if (dictionary.find(search) != dictionary.end()) {
            temp = search;
            pos++;
        } 
        else {
            iter = dictionary.find(temp);
            answer.push_back((*iter).second); 
            dictionary.insert(make_pair(search, ++size));
            temp = "";
            search="";
        }
    }

    iter = dictionary.find(temp);
    answer.push_back((*iter).second);

    cout<<"[";
    for(i=0; i<answer.size()-1; i++) {
        cout<<answer[i]<<", ";
    }
    cout<<answer[i]<<"]"<<endl;
}

 

---

추가적으로 공부용으로 코드 돌아가는거 종이에 써가면서 while문 안쪽 코드 분석도 해봤다.

(input값으로 KAKAO가 들어갔을때)

 

 

pos 값 : 0	pos 값 : 1	pos 값 : 1	pos 값 : 2
search = K	search = KA	search = A	search = AK
if문에 걸림	else문에 걸림	if문에 걸림	else문에 걸림
temp = K pos++;	temp = K → answer에 11(K) 들어감 dictionary에 (KA, 27)	temp = A pos++;	temp = A → answer에 1(A) 들어감 dictionary에 (AK, 28)
pos 값 : 2	pos 값 : 3	pos 값 : 4	pos 값 : 4
search = K	search = KA	search = KAO	search = O
if문에 걸림	if문에 걸림	else문에 걸림	if문에 걸림
temp = K pos++;	temp = KA pos++;	temp = KA → answer에 28(KA) 들어감 dictionary에 (KAO, 29)	temp = O pos++;  → '/0'만나서 반복문 끝

 

그러고 나서 마지막에 temp = O였으므로 O를 사전에서 찾은 뒤, O의 인덱스값 15를 answer에 넣으면 된다. 

위와같이 정답이 잘 나오는 것을 확인할 수 있다!