카카오 공채 코딩테스트:: 압축 (C++)

 

 

* 생각한 아이디어 및 문제 풀이

 

0. 입력은 그냥 string으로 받는다.
1. 기본 A~Z를 vector 형태의 사전에 넣고 초기화 시켜준다. (0번 제외, 1~26번까지)
2. 사전에서 현재 입력에 일치하는 글자를 사전에서 찾았다면 해당 인덱스를 output 벡터에 push한다.
3. 첫글자와 다음 글자의 연속이 사전에 있는지 서치하고, 없다면 사전에 추가한다.
4. 다음 순서에도 해당 글자가 존재하는지 확인하고 없다면 추가한다. 
5. 다시 2번으로 돌아가서 벡터의 끝을 순회할 때 까지 반복한다.
6. 최종 output 벡터를 출력한다.

 

 

* 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<string> v = {"","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
string str; // 현재 검색하는 글자

int dict(string s)  {
    for(int i = 0; i < v.size(); i++) {
        if(s == v[i]) { // 찾은 경우
            return i;
        }
    }
    return -1; // 못찾은 경우
}

int main(){
    ios::sync_with_stdio(false); 
    string input;
    cin >> input;

    vector<int> output;
    int value, idx, i=0;

    str = input[i]; // 초기 설정
    while(i<input.size()){
        idx = dict(str);
        if(dict(str) > -1){ // 사전에서 찾은 경우
        value = idx;
            if(i==input.size()-1){ // 사전값을 저장해둠
                output.push_back(value);
            }
            i++;
            str += input[i];
        }
        else{ // 사전에서 못 찾은 경우
            output.push_back(value); //
            v.push_back(str); // 없는 단어 추가
            str = input[i]; //이어지는 단어로 초기화
        }
    }
    for(auto& j :output){
        cout << j << ' ';
    }
}

 

 

* 회고

알파벳 초기화 부분을 최적화 시키면 더 좋을 것 같다.

코딩테스트 문제를 처음 풀어봤는데 문제 자체를 잘 이해하지 못해서 다른 사람의 코드를 참고하여 풀었다는 점이 스스로 아쉽다.

지금까지 비교적 쉬운 난이도의 문제만 풀었던 것 같다.

앞으로 이런 문제들을 자주 풀어보아야 겠다.

 

 

* 문제 링크 :

https://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/

카카오 신입 공채 3차 코딩 테스트 문제 해설

 

* 참고 링크 :

https://twoearth.tistory.com/14

[카카오 공채] 압축