새로운 문자열을 배열에 추가하며 찾는 문제이다.
문제 해결 전략
문자열을 저장한 배열에 새로운 문자열이 있는지 확인 후 없으면 배열에 추가해야 한다.
즉, 매번 배열을 탐색하며 문자열의 존재 유무를 확인해야 한다는 것이다.
이 과정을 쉽게하기 위해 map 자료구조를 이용하였다.
map은 find 함수를 제공하기 때문에 배열을 순차적으로 탐색하는 것보다 시간복잡도도 낮고 사용하기도 쉽다.
문자열이 map에 존재하는지 확인 후 존재한다면 문자열 늘린다.
만약 존재하지 않는다면 늘리기 전 문자열을 map에 추가 하는 것이다.
코드
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> solution(string msg) {
vector<int> answer;
map<string, int> m;
for(int i=1;i<27;i++){
string alpha = "";
char tmp = 'A' + i - 1;
alpha += tmp;
m.insert(make_pair(alpha, i));
}
for(int i=0;i<msg.size();i++){
string str = "";
str += msg[i];
int tmp = 0;
while(1){
if(m.find(str) != m.end()){
tmp = m[str];
i++;
str += msg[i];
}else{
answer.push_back(tmp);
m.insert(make_pair(str,m.size()+1));
i--;
break;
}
}
}
return answer;
}
출처 : https://programmers.co.kr/learn/courses/30/lessons/17684