[2025.02.05] 대충 만든 자판

문제 설명

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

 

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

 

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

 

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

 

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

 

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

 

 

제한사항

• 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의 원소는 알파벳 대문자로만 이루어져 있습니다.

 

 

입출력 예

keymap			targets	result	설명
["ABACD", "BCEFD"]			["ABCD", "AABB"]	[9, 4]	"ABCD"의 경우, 1번 키 한 번 → A 2번 키 한 번 → B 2번 키 두 번 → C 1번 키 다섯 번 → D 따라서 총합인 9를 첫 번째 인덱스에 저장합니다. "AABB"의 경우, 1번 키 한 번 → A 1번 키 한 번 → A 2번 키 한 번 → B 2번 키 한 번 → B 따라서 총합인 4를 두 번째 인덱스에 저장합니다. 결과적으로 [9, 4]를 return 합니다.
["AA"]			["B"]	[-1]	"B"의 경우, 'B'가 어디에도 존재하지 않기 때문에 -1을 첫 번째 인덱스에 저장합니다. 결과적으로 [-1]을 return 합니다.
["AGZ", "BSSS"]			["ASA", "BGZ"]	[4, 6]	"ASA"의 경우, 1번 키 한 번 → A 2번 키 두 번 → S 1번 키 한 번 → A ㄸ라서 총합인 4를 첫 번째 인덱스에 저장합니다. "BGZ"의 경우, 2번 키 한 번 → B 1번 키 두 번 → G 1번 키 세 번 → Z 따라서 총합인 6을 두 번째 인덱스에 저장합니다. 결과적으로 [4, 6]을 return 합니다.

 

 

문제 풀이

풀이 언어 : C++

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

using namespace std;

// ch를 작성하기 위한 최소 클릭 회수 구하기
int press_minimize(char ch, vector<string> keymap)
{
    vector<int> how_many_press; // 키 별로 눌러야 하는 횟수
    
    // 키별로 눌러야 하는 횟수 계산
    for(int key; key<keymap.size(); key++)
    {
        // 키를 눌러 ch를 작성할 수 있다면
        if(find(keymap[key].begin(), keymap[key].end(), ch)!=keymap[key].end())
        {
            how_many_press.push_back(find(keymap[key].begin(), keymap[key].end(), ch)-keymap[key].begin()); // how_many_press에 저장
        }
    }
    
    // 작성 가능 여부 확인
    if(how_many_press.size()==0) // 작성할 수 없다면
    {
        return -1; // -1 리턴
    }
    else // 작성 가능하다면
    {
        return (*min_element(how_many_press.begin(), how_many_press.end()))+1; // 눌러야하는 최소 횟수 리턴
    }
    
}
vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    int push_count;
    for(int i=0; i<targets.size(); i++)
    {
        push_count=0; // 키 클릭 횟수 초기화
        for(int j=0; j<targets[i].size(); j++)
        {
            // 문자를 누를 키가 없을 경우
            if(press_minimize(targets[i][j], keymap)==-1)
            {
                push_count=-1; // -1 결과값(작성불가)반복문 탈출
                break; // 반복문 중단
            }
            else // 키가 있을 경우
            {
                push_count+=press_minimize(targets[i][j], keymap); // 최소 클릭값 누적 저장
            }
        }
        answer.push_back(push_count); // targets[i]를 작성하기 위해 눌러야 하는 최소 횟수 저장
    }
    return answer;
}

 

targets의 있는 문장 한 문장씩, 문장의 한 글자 한 글자마다 최소 몇번 키를 눌러야 입력할 수 있는지 알아낸 뒤 모두 더해서 답을 내면 되는 문제이다. 만약 한 글자씩 키를 누르는 횟수를 알아내다가 입력할 수 없는 문자를 만나면 즉시 -1을 저장하고 다음 문장으로 넘어간다.

 

문장 하나씩, 한 글자 한 글자를 살펴볼 반복문부터 작성해준다. 문장을 돌릴 for문 하나와 글자 하나씩을 볼 for문 하나를 준비해 총 2개의 for문을 돌려준다.

 

매개변수로 문자와 keymap을 받으면 해당 문자를 입력하기 위해 최소 몇 번 키를 눌러야하는지 반환하는 함수를 만들어 준다. 이름은 press_minimize로 매개변수로는 문자인 ch와 solution의 매개변수로 들어온 keymap을 그대로 받아온다.

같은 문자가 자판 전체에 여러번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당되는 경우도 있다. 이 말은 즉 keymap에 적힌 모든 키를 다 확인해야 한다는 것이다. 그리고 키마다 몇 번 눌러야 해당 문자가 나올지 다를 수도 있기 때문에 문자를 입력하는 많은 방법 중 최소로 누르는 경우를 골라 알려주어야 한다.

이를 구현하기 위해 일단 모든 키에서 해당 문자를 입력하려면 몇 번을 눌러야 하는 int형 벡터 how_many_press에 저장하기로 하였다. for문을 이용해 모든 키를 살펴본다. find() 함수를 이용하여 만약 해당 키에 ch를 입력하는 방법이 존재한다면 가장 빨리 입력할 수 있는 횟수로 how_many_press에 저장한다. 만약 그 키로 ch를 입력할 수 없다면 아무 것도 하지 않는다.

모든 키를 훑어보고 난 후 ch는 입력이 가능한 문자인지, 가능하다면 최소 몇 번을 눌러야 하는지를 반환한다. 만약 how_many_press에 아무 요소가 없다면 여직 훑어본 키에서 ch를 입력할 방법이 없었다는 이야기이므로 작성 불가를 나타내기 위해 -1을 반환한다. 하지만 만약 요소가 있다면 입력할 방법이 존재한다는 것이다. 방법이 존재한다면 ch를 입력할 수 있는 경우들의 키 누름 횟수를 저장한 how_many_press에서 최소값을 찾아 반환해야할 것이다.

 

다시 solution의 for문으로 돌아오자. 핵심은 함수가 거의 다 했으니 이제 for문을 돌며 남은 처리를 해야한다. 문자를 입력할 수 있는지 없는지부터 확인한다. 이는 아까 만든 함수를 이용한다. 함수의 매개변수에 문자와 keymap을 넣고 누를 키가 있는지 확인한다. 키가 없다면 -1을 반환했을 것이니 함수의 리턴값이 -1이라면 push_count를 -1로 하고 반복문을 즉시 중단한다. 그러면 반복문 밖으로 나가 결과값이 -1을 answer에 저장한다. 문장에서 한 글자만 입력하지 못해도 결국 입력하지 못하는 문장이기 때문이다.

만약 -1이 아닌 다른 수가 나온다면 키가 존재한다는 것이다. 키가 존재할 때는 함수의 return 값을 push_count에 누적하여 저장하고 다음 문자로 넘어간다. 이렇게 한 문장이 끝날 때까지 계속 입력할 수 있는 문자라면 push_count에 횟수가 더해져 쌓여있을 것이다. 이 값을 문장이 끝나면 push_count값을 answer에 저장한다.

 

 

문제 링크

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

프로그래머스