메모장

정답처리 된 코드지만 , 가독성이 안좋게 구성이 되었다.

하나의 target을 정한뒤 keymap을 벡터를 탐색해서 해당 문자를 찾는것으로 설계를 하다보니 반복문 다중으로 많이 사용되었음. 

플로우차트는 

0.target의 문자열을 길이기준으로 오름차순 정렬

ex) ABCD,ABC,ABCDE -> ABC,ABCD,ABCDE

1.비교할 target 선정 

1-1.target의 char(단일문자)하나를 선정
2.target_Char 와 keymap과의 비교 시작

2-1.keymap_char_index 설정 ( keymap 리스트에 공통적으로 적용되는 인덱스)

2-2. keymap_list Roop 시작

2-3.비교 시작  

2-3-1.(같은 문자를 찾은경우) 2-1로 돌아감,roop한 횟수를 answer에 저장

2-3-2.(같은 문자를 못 찾은경우) 2-1로 돌아감,,다시 탐색

2-3-3.(roop를 다 돌렸지만 해당 target 문자를 못찾을경우) answer 벡터에 -1 대입후 반복문 탈출 및 1번으로 돌아감

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(string keymap1, string keymap2)
{
    //글자갯수로 오름차순 정렬
    return keymap1.length() < keymap2.length();
}

bool char_compare(char target_char,vector<string> keymap,int c)
{
    for (int d = 0; d < keymap.size(); d++)
    {
    	//해당 target의 문자 index가 문자열 길이 보다 크거나 같을경우, 그 반복문 본문 스킵
        //ex)ABC(문자열 길이 3) targer index (4) -> skip 
        if (keymap[d].length() <= c)
        {
            continue;
        }

        char key_char = keymap[d].at(c);

        //2-3.비교시작
        if (target_char == key_char)
        {
            //2-3-1.(같은 문자를 찾은경우) 2-1로 돌아감,roop한 횟수를 answer에 저장
            return true;
        }

    }

    return false;
}

vector<int> solution(vector<string> keymap, vector<string> targets)
{
    //keymap 문자열 길이기준으로 오름차순 정렬 
    sort(keymap.begin(), keymap.end(), compare);
    int roop_count = keymap.back().length(); // target중 제일 긴문자를 roop횟수로 설정
	
	//answer를 target벡터 갯수만큼 초기화
    vector<int> answer;
    for (int i = 0; i < targets.size(); i++)
    {
        answer.push_back(0);
    }
    bool fail_check = false;

    for (int a = 0; a < targets.size(); a++)
    {
        //1.비교할 target 선정
        string target_str = targets[a];// targets 문자열 정의
        int target_length = target_str.length();

        for (int b = 0; b < target_length; b++)
        {
            //1-1.target Char 설정
            char target_char = target_str.at(b);

            //2.target_Char vs keymap_list (비교)
            //2-1.keymap_char_index 설정( 리스트에 공통)
            
            //c : target_char_index
            for (int c = 0; c < roop_count; c++)
            {
                //2-2.keymap_list_index 루프 시작
                if (char_compare(target_char, keymap, c))
                { 
                    answer[a] += c + 1;
                    break;
                }
                
          	   //해당되는 글자를 못찾을경우 -1과 bool값 변경
                if (c == roop_count - 1)
                {
                    answer[a] = -1;
                    fail_check = true;
                }
            }
			
			//해당 문자열은 출력 못하므로 문자열 반복문 탈출 
            if (fail_check)
            {
                fail_check = false;
                break;
            }

        }
    }

    return  answer;
}

이 풀이는 target을 먼저 탐색하기 전에 , keymap을 루프를 돌려 해당 문자를 출력하기 위한 최소의 횟수를 미리 리스트화 한뒤 target에 접근 하는 방식이다.

플로우차트는

1.26개(알파벳갯수)의 사이즈의 벡터를 100000(MARKER)로 전부 초기화

1-1.keymap을 기준으로 루프를 돌려 table에 해당 문자열을 찾기위해 최소 횟수 탐색
ex) 

target = { ABACD , BECFD }

첫번째 루프 (ABACD)

table[0] = 1 // 1=min(100000 , 1) 알파벳 A

table[1] = 2 // 1=min(100000 , 2) 알파벳 B

table[0] = 1 // 1=min(1 , 1) 알파벳 A

table[2] = 4 // 4=min(100000 , 4) 알파벳 C

table[3] = 5 // 5=min(100000 , 5) 알파벳 D

두번째 루프 (BCEFD)

table[1] = 1 // 1=min(2 , 1) 알파벳 B

table[2] = 2 // 2=min(4 , 2) 알파벳 C

table[4] = 3 // 1=min(100000 , 3) 알파벳 E

table[5] = 4 // 4=min(100000 , 4) 알파벳 F

table[3] = 5 // 5=min(5 , 5) 알파벳 D

최종 결과물
table[0] = 1  // 알파벳 A를 출력하기 위한 최소 횟수

table[1] = 1 // 알파벳 B를 출력하기 위한 최소 횟수

table[2] = 2 // 알파벳 C를 출력하기 위한 최소 횟수

table[3] = 5 // 알파벳 D를 출력하기 위한 최소 횟수

table[4] = 3 // 알파벳 E를 출력하기 위한 최소 횟수

table[5] = 4 // 알파벳 F를 출력하기 위한 최소 횟수

table[6] = 100000 // 알파벳 G를 출력하지 못함
... 

 이런식의 roop를 통해 미리 알파벳의 최소 루트를 구해놓은뒤 작업을 한다 .

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;

    const int MARKER = 1000000; //  MARKER : 사용하지않는것을 표시
    vector<int> table(26, MARKER);  //26개(알파벳 갯수)의 벡터 사이즈 설정 , MARKER(100000)으로 초기화
   
   //keymap를 루프 둘려 각 단일문자를 최소의 횟수로 찾아가는지 탐색 
    for (const auto& v : keymap)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            table[v[i] - 'A'] = min(table[v[i] - 'A'], i + 1);
        }
    }

    for (const auto& str : targets)
    {
        int total = 0;
        for (const auto c : str)
        {
            //MARKER와 같으면 이 문자는 출력할수 없다는 뜻
            if (table[c - 'A'] == MARKER)
            {
                //결과값 -1과 해당 문자열 탈출 
                total = -1;
                break;
            }
            else
            {
				//위에서 구한 해당 문자의 최소 출력횟수를 total에 더함
                total += table[c - 'A'];
            }
        }
		
        //push_back과 같은 의미지만 자료형이 같을경우 사용할수 있는 push_back
        answer.emplace_back(total);
    }

    return answer;
}