[코딩테스트] 대충 만든 자판

매일매일 코딩테스트

오늘의 잔디채우기는

프로그래머스 Lv.1 - 대충 만든 자판

문제 설명

휴대폰 자판은 컴퓨터 키보드와 다르게 한 키에 여러 개의 문자가 할당돼 있을 수 있다.
한 문자를 입력하려면 해당 키를 할당된 순서대로 몇 번 눌러야 한다.

예를 들어

• "A", "B", "C"가 1번 키에 순서대로 할당돼 있다면
  • 1번 누르면 "A"
  • 2번 누르면 "B"
  • 3번 누르면 "C"

---

문제 조건 요약

• 각 줄마다 키가 할당된 문자들이 담긴 문자열 배열 keymap
• 입력해야 하는 문자열 목록 targets
• 목표: targets의 각 문자열을 작성하기 위해 눌러야 하는 최소 키 누름 수 구하기
• 특정 문자가 keymap 어디에도 없으면 -1 반환

---

입출력 예시

---

풀이 C++

내 풀이

• keymap은 한 줄이 한 키에 대응된다고 보고,
• targets의 각 문자에 대해
  • 모든 keymap 줄을 확인하면서
  • 해당 문자가 몇 번째에 있는지 찾고,
  • 그 중 최솟값을 사용

문제

• total의 초기화
  • total을 전체 반복문 밖에 두어서, targets의 각 단어마다 결과가 초기화되지 않고 누적되어 결과가 틀림

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

int findIndex(string keymap,char ch)
{
    //for(int i = 0; i < keymap.length(); i++)
    {
        size_t pos = keymap.find(ch);
        
        if (pos != string::npos)
        {
            return pos + 1;
        }
        else
            return -1;
    }
}

vector<int> solution(vector<string> keymap, vector<string> targets) 
{
    vector<int> answer;
    
    for(int i = 0; i < targets.size(); i++)
    {
        int total = 0;
        
        for(int j = 0; j < targets[i].length();j++)
        {
            int minValue = 101;
            char ch = targets[i][j];
            
            for(int k = 0; k < keymap.size(); k++)
            {
                int Index = findIndex(keymap[k],ch);
                
                if(Index != -1)
                {
                    minValue = min(minValue,Index);    
                }
            }
            
            if (minValue == 101)  // 한 번도 못 찾음
            {
                total = -1;
                break;
            }
            else
                total += minValue;
        }
        answer.push_back(total);
    }
    return answer;
}

 

---

최적의 풀이

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

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

    // 문자 별 최소 키 누름 수 미리 저장
    for (const string& key : keymap)
    {
        for (int i = 0; i < key.size(); i++)
        {
            char ch = key[i];
            if (charMinPress.count(ch))
                charMinPress[ch] = min(charMinPress[ch], i + 1);
            else
                charMinPress[ch] = i + 1;
        }
    }

    // 각 target 문자열 처리
    for (const string& word : targets)
    {
        int total = 0;
        for (char ch : word)
        {
            if (charMinPress.count(ch))
                total += charMinPress[ch];
            else {
                total = -1;
                break;
            }
        }
        answer.push_back(total);
    }

    return answer;
}