<문제 소개>
<소스 코드>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> solution(vector<string> keymap, vector<string> targets)
{
vector<int> answer;
map<char, int> key;
// 키맵을 돌면서 각 단어별 찾아야되는 횟수를 미리 파악
for(int i = 0; i < keymap.size(); i++)
{
string curStr = keymap[i]; // 현재 문장
for(int j = 0; j < curStr.size(); j++)
{
char curWord = curStr[j]; // 현재 단어
// 처음 나오는 단어이거나,
// 지금 단어를 누른 횟수가 원래 단어 누르는 횟수보다 더 작은 경우
// -> 최소 횟수로 변경
if(key[curWord] == 0 || key[curWord] > j + 1)
{
key[curWord] = j + 1;
}
}
}
// 타겟들을 돌면서 문장별 작성여부 판단 및 횟수체크
for(int i = 0; i < targets.size(); i++)
{
string curStr = targets[i]; // 현재 문장
answer.push_back(0);
for(int j = 0; j < curStr.size(); j++)
{
char curWord = curStr[j]; // 현재 단어
// 문자를 작성할 수 없는 경우
if(key[curWord] == 0)
{
answer[i] = -1;
break;
}
answer[i] += key[curWord];
}
}
return answer;
}<풀이과정>
1. map을 이용해 각 단어별 찾아야 되는 횟수를 매핑하는 맵 key를 선언한다.
2. keymap의 원소들을 돌면서 key를 완성해준다.
3. 이중 for문을 이용해 keymap의 현재 단어에 접근하고, key의 키로 현재 단어 curWord를 넣었을 때 처음 넣는 경우 이거나 이전에 넣었던 값이 지금 값보다 더 큰 경우 지금의 값으로 단어별 최소 횟수를 변경해준다.
4. 위의 과정이 끝나면 key가 완성되었으므로 이제 targets의 각 원소들을 돌면서 문장들의 작성여부와 작성횟수를 체크해준다.
5. 이중 for문을 돌면서 targets의 단어에 접근할건데 그 전에 각 문장을 반복하는 외부 for문을 한번씩 돌때마다 answer에 0을 넣어 벡터를 늘려주고, 해당 자리에 현재 문자의 작성횟수를 담는다.
6. 내부의 반복에서는 targets의 현재 단어에 접근하여 key로 해당 단어의 존재여부부터 파악한 뒤 없다면 문자를 작성할 수 없는 경우이므로 answer의 현재 값 answer[i]를 -1로 바꿔주고 반복을 끝낸다.
7. 단어가 key에 존재한다면 해당 단어의 접근횟수만큼 answer에 더해준다.
8. 위의 반복이 모두 끝난뒤 answer를 리턴해준다.
<코멘트>
처음에는 4중 for문을 썼다가 시간초과는 아니지만 틀리기도 했고, 이건 너무 아닌 것 같다 싶어서 지금 방법으로 바꾸었다.
이 방법이 훨씬 깔끔하고 좋은 것 같다!
처음에 문자 작성할 수 없는 경우를 판단하는 것을 내부 for문이 다 돈 뒤 answer가 0인 경우에만 -1을 리턴했는데 생각해보니 "ABC", "ABD" 이렇게 처음엔 잘 더해나가다가 중간이나 마지막 즈음에 없는 단어가 나올 경우 answer가 0이 아니더라도 -1을 리턴해야하는 경우를 놓치고 있었다. 그래서 14번 이후로 실패가 나와서 뭐지? 하다가 질문하기에서 반례를 보고서야 틀린 점을 겨우 알 수 있었다.
<제출결과>
