문제 160586. 대충 만든 자판

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

난이도 : Lv.1 

 

문제 요약 설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

입력

• 1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap
• 문자열들이 담긴 문자열 배열 targets

입력 제한

• 1 ≤ keymap의 길이 ≤ 100
  • 1 ≤ keymap의 원소의 길이 ≤ 100
  • keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
    • 예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
  • keymap의 원소의 길이는 서로 다를 수 있습니다.
  • keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
• 1 ≤ targets의 길이 ≤ 100
  • 1 ≤ targets의 원소의 길이 ≤ 100
  • targets의 원소는 알파벳 대문자로만 이루어져 있습니다.

입력 예제

// input
["ABACD", "BCEFD"] // keymap
["ABCD","AABB"] // targets

// ans
[9, 4]

 

풀이 방식

 

우선 각 키맵에서 문자를 얻기 위해 눌러야 하는 최소 횟수를 저장하는 배열(v1)이 하나 필요하다. 참고로, 알파벳만 매핑되기 때문에 배열의 크기를 고정(27개정도?)할 수 있지만 대신 map을 사용했다.(map 애호가)

하지만, 각 키맵에는 여러 번 같은 문자가 할당되어있을 수 있으므로, 차례로 키맵을 읽었을 때 눌렀을 때 처음 나온 문자만 횟수를 저장한다.

배열을 전부 만들었다면, 해당 배열을 이용해 target에 있는 문자열의 문자를 얻기 위해 눌러야 하는 최소 횟수를 구하면된다. 구하는 방법은 모든 키맵들 중에서 해당 문자를 얻는데 필요한 누른 횟수가 가장 적은 횟수를 문자열의 문자 개수만큼 반복하여 얻고 더하면된다(sum변수에 저장). 반복을 마치고 중간에 얻을 수 없는 문자가 나오지 않았다면 sum을 정답에 추가한다. 얻을 수 없는 문자가 있었다면 sum대신 -1을 저장한다.

정답 코드 

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

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    vector<map<char, int>> v1(keymap.size()); // 각 키맵에서 문자를 얻기 위해 눌러야 하는 최소 횟수를 저장
    
    for(int i = 0; i < keymap.size(); i++){   
        for(int j = 0; j < keymap[i].length(); j++){
            char c = keymap[i][j];
            // 한 번도 저장되지 않았을 때만 횟수를 저장(최소로 누르기 위함)
            if(v1[i][c] == 0){       
                v1[i][c] = j+1;
            }
        }
    }
    
    // 각 문자열
    for(int i = 0; i < targets.size(); i++){
        int sum = 0;
        // 각 문자열의 문자
        for(char c : targets[i]){       
            // 해당 문자를 얻기 위한 최소 횟수를 keymap들에서 찾음
            int temp_n = 101;
            for(int j = 0; j < v1.size(); j++){
                if(v1[j][c] == 0) continue;
                temp_n = min(temp_n, v1[j][c]);
            }
            
            // 해당 문자를 얻을 수 없는 경우, -1을 저장하고, 
            // 루프(해당 문자열을 얻기 위한 최소 클릭 횟수 구하기)를 나온다.
            if(temp_n == 101){
                sum = -1;
                break;
            }
            else{
                sum += temp_n;
            }
            
        }
        // 최소 클릭 횟수를 저장한다.
        answer.push_back(sum);
    }
    return answer;
}