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;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 1744번 수 묶기 (0) | 2021.08.04 |
---|---|
[C++] 백준 4358번 생태학 (0) | 2021.08.04 |
[C++] 프로그래머스 - N진수 게임 (0) | 2021.05.18 |
[C++] 프로그래머스 - 캐시 (0) | 2021.05.14 |
[C++] 프로그래머스 - 프렌즈 4블록 (0) | 2021.05.14 |