(C++) 2018 KAKAO BLIND RECRUITMENT [3차] - 압축

1. 문제

programmers.co.kr/learn/courses/30/lessons/17684

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

 

2. 풀이

주어진 msg와 dict 두개의 배열이 필요하다. 

 

dict 배열

i	1	2	...	24	25	26
내용	A	B		X	Y	Z

msg

K	A	K	A	O
^index+length-1

 

검색을 시작하기 전

word_length = 1;

 

• search_word에 현재 index 에 있는 글자를 넣는다.

search_word = "K"

 

• 현재 index를 dict 배열에서 찾는다. 
• 찾을 시 -> dict의 i를 word_index에 넣는다.

dict[11] == "K"이므로 word_index = 11

 

• word_length 를 1증가 시킨다. 

word_length = 2;

 

• search_word에 다음 글자를 넣는다. 

search_word = "KA"

 

• 못찾을시 -> 찾던 search_word를 dict 맨 뒤에 넣은 후, index를 증가시켜서 msg의 다음 글자를 찾는다. 

K	A	K	A	O	KA
	^index+length-1

dict.push_back = "KA"

index = index + word_length -1

search_word = "A"

 

위 과정을 반복한다. 

 

 

3. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    vector <string> dict;
    
    for(int i = 0; i < 26;i++){
        string element = "";
        char a = i+65;
        element.push_back(a);
        dict.push_back(element);
    }
    
    int index = 0;
    int word_index;
    
    while(index < msg.length()){
        int word_length = 1; //찾아야되는 글씨 길이
        string search_word =""; // 찾아야 되는 글씨    
        bool flag = true;
        while(flag){ //딕셔너리에서 인덱스 글자를 발견을 못할때까지
            flag = false;
            search_word.push_back(msg[index+word_length-1]); //찾았으면 다음 글자를 찾아보기... 
            for(int i = 0; i < dict.size();i++){
                if(search_word == dict[i]){     //dict에 찾는 단어가 있으면
                    word_index = i;             //찾은 인덱스
                    flag = true;                //찾았음
                    word_length ++;             //다음 글자 찾기
                    break;
                }       
            }
        }
        dict.push_back(search_word);
        answer.push_back(word_index+1);
        index = index+word_length-1;
    }

    return answer;
}

 

4. 그외

한방에 풀었다.. 호호 넘모 신난당...

 

카카오 문제를 풀다보며 느끼는 점 : 

반복문 쓰는 것을 두려워하지말자... 노가다가 제일 빠른 방법일 수도,,