문제 설명
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 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
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
'Code KATA > 알고리즘 코드카타' 카테고리의 다른 글
[2025.02.07] 햄버거 만들기 (1) | 2025.02.07 |
---|---|
[2025.02.06] 둘만의 암호 (1) | 2025.02.06 |
[2025.02.24] 문자열 나누기 (0) | 2025.02.04 |
[2025.02.03] 체육복 (1) | 2025.02.03 |
[2025.01.31] 로또의 최고 순위와 최저 순위 (0) | 2025.01.31 |