끄적끄적 코딩
article thumbnail
Published 2021. 5. 26. 14:57
[C++] 프로그래머스 - 압축 알고리즘

2018 KAKAO BLIND RECRUITMENT (2018 카카오 블라인드 채용 문제)

문자가 입력되면 알고리즘에 맞게 압축하는 문제입니다.

---사전---
A - 1
B - 2
C - 3
....
X - 25
Z - 26

사전에는 기본 알파벳이 압축되어있습니다.

1. 입력값 + (사전에 가장 긴 길이의 문자 길이) - 1 만큼의 길이에 문자를 사전에서 탐색
1-1. 없을 시 위의 길이에서 -1만큼 길이에 문자를 사전에서 탐색
1-2. 문자 길이가 0보다 클 경우 1-1을 반복
2. 찾은 문자의 숫자를 answer에 삽입
2-1. 찾은 문자의 길이만큼 인덱스를 이동
3. 찾은 문자에 다음 문자를 붙인 문자를 사전에서 탐색
4. 없을 경우 사전에 추가
4-1. 해당 문자의 길이가 (사전에 가장 긴 길이의 문자 길이)보다 클 경우 값을 대체
5. 1~4를 문자를 전부 탐색할때까지 반복



코드

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

vector<int> solution(string msg)
{
  int k;
  int len = 1;
  int textLen;
  int maxRange;
  char alp;
  bool check;
  bool exist;
  string s = " ";
  string text;
  string mixText;
  vector<int> answer;
  vector<pair<int, string>> dic;

  for (int i = 1; i <= 26; ++i)
  {
    alp = 'A' + i - 1;
    s = alp;
    dic.push_back(make_pair(i, s));
  }

  for (int i = 0; i < msg.length();)
  {
    check = false;
    for (int j = 0; j < len; ++j)
    {
      if (i + len > msg.length() + j)
      {
        maxRange = i + len - j - msg.length();
        text = msg.substr(i, len - maxRange);
      }
      else
      {
        text = msg.substr(i, len - j);
      }
      for (k = 0; k < dic.size(); ++k)
      {
        if (text == dic[k].second)
        {
          answer.push_back(dic[k].first);
          check = true;
          break;
        }
      }
      if (check)
      {
        break;
      }
    }
    if (check)
    {
      i += dic[k].second.length();
      if (i >= msg.length())
      {
        break;
      }
      exist = false;
      mixText = dic[k].second + msg[i];
      for (int l = 0; l < dic.size(); ++l)
      {
        if (mixText == dic[l].second)
        {
          exist = true;
        }
      }
      if (!exist)
      {
        dic.push_back({dic.size() + 1, mixText});
        textLen = mixText.length();
        len = max(len, textLen);
      }
      continue;
    }
  }
  return answer;
}
 

검색 태그