[프로그래머스][C++] 대충 만든 자판
대충 만든 자판
문제 링크
분석
targets 배열의 각 단어에 대해 입력하기 위한 최소 횟수를 합산하여 결과값을 구합니다.
만약 키보드에 존재하지 않는 문자가 있다면, 해당 단어는 입력할 수 없으므로 -1을 반환해야 합니다.
최소 횟수를 구하는 방법은 브루트포스 방식과 미리 최소 입력 횟수를 저장한 뒤 조회하는 방식이 있습니다.
풀이
매번 특정 문자가 존재하는지 최소 인덱스를 찾는 방법입니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<string> keymap, vector<string> targets) {
vector<int> answer(targets.size());
// targets 순회
for(int i = 0; i < targets.size(); ++i)
{
// targets[i] 순회
for (int j = 0; j < targets[i].size(); ++j)
{
// 찾은 글자의 인덱스를 저장할 변수
int keyIndex = 101;
// keymap 순회
for (auto key : keymap)
{
int CurkeyIndex = key.find(targets[i][j]);
// targets[i][j]의 글자가 keymap에 있는 경우
if (CurkeyIndex != string::npos)
{
// 인덱스의 크기를 비교하고 작은 인덱스를 저장
keyIndex = (CurkeyIndex < keyIndex) ? CurkeyIndex : keyIndex;
}
}
// 글자를 찾았다면
if (keyIndex != 101)
{
answer[i] += keyIndex + 1;
}
// 글자를 찾지 못했다면
else
{
answer[i] = -1;
break;
}
}
}
return answer;
}
std::unordered_map을 사용하여 각 문자에 대한 최소 입력 횟수를 미리 계산한 후, 조회하는 방법입니다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> solution(vector<string> keymap, vector<string> targets) {
vector<int> answer;
// 각 문자에 대한 최소 입력 횟수를 저장
unordered_map<char, int> minKeyPress;
// keymap 순회
for (const string& keys : keymap)
{
// keys 순회
for (int i = 0; i < keys.length(); i++)
{
// minKeyPress에 문자에 대한 입력 횟수가 있다면
if (minKeyPress.find(keys[i]) != minKeyPress.end())
{
// 최소값을 찾아 저장
minKeyPress[keys[i]] = (minKeyPress[keys[i]] < i + 1) ? minKeyPress[keys[i]] : i + 1;
}
// minKeyPress에 문자에 대한 입력 횟수가 없다면
else
{
// 문자에 대한 입력 횟수 저장
minKeyPress[keys[i]] = i + 1;
}
}
}
// targets 순회
for (const string& target : targets)
{
// 총 입력 횟수
int totalPress = 0;
// 입력 가능한 문자인지 저장
bool isPossible = true;
// target 순회
for (const char& c : target)
{
// 키보드에 없는 문자인 경우
if (minKeyPress.find(c) == minKeyPress.end())
{
// 입력 불가능한 문자로 값 저장 및 반복문 탈출
isPossible = false;
break;
}
// 키보드에 있는 문자인 경우이므로, 현재 문자에 필요한 입력 횟수를 가져와 총 합 저장
totalPress += minKeyPress[c];
}
// 입력 가능한 문자인 경우 총 합을 저장하고, 불가능한 문자인 경우 -1을 저장
answer.push_back(isPossible ? totalPress : -1);
}
return answer;
}
성능 요약
매번 특정 문자가 존재하는지 최소 인덱스를 찾는 성능입니다.
시간 복잡도는 $O(nmpk)$입니다.
targets를 순회하는 반복문 $O(n)$targets[i]를 순회하는 반복문 $O(m)$kemap을 순회하는 반복문 $O(p)$find함수의 최악의 경우 $O(k)$- $O(n) \times O(m) \times O(p) \times O(k)$
- $O(n \times m \times p \times k)$
공간 복잡도는 $O(n)$입니다.
answer은targets의 크기만큼 할당 $O(n)$
테스트 1 〉 통과 (0.18ms, 4.02MB)
테스트 2 〉 통과 (0.26ms, 4.15MB)
테스트 3 〉 통과 (0.15ms, 4.22MB)
테스트 4 〉 통과 (0.18ms, 4.02MB)
테스트 5 〉 통과 (0.10ms, 4.15MB)
테스트 6 〉 통과 (0.39ms, 3.63MB)
테스트 7 〉 통과 (0.10ms, 4.21MB)
테스트 8 〉 통과 (0.17ms, 4.21MB)
테스트 9 〉 통과 (0.07ms, 4.45MB)
테스트 10 〉 통과 (0.08ms, 3.69MB)
테스트 11 〉 통과 (0.01ms, 3.63MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.01ms, 4.22MB)
테스트 14 〉 통과 (4.41ms, 4.15MB)
테스트 15 〉 통과 (7.71ms, 3.68MB)
테스트 16 〉 통과 (8.65ms, 4.14MB)
테스트 17 〉 통과 (6.40ms, 4.15MB)
테스트 18 〉 통과 (3.40ms, 4.2MB)
테스트 19 〉 통과 (4.21ms, 4.21MB)
테스트 20 〉 통과 (3.46ms, 4.21MB)
테스트 21 〉 통과 (4.64ms, 4.03MB)
테스트 22 〉 통과 (5.83ms, 4.22MB)
테스트 23 〉 통과 (7.37ms, 4.02MB)
시간 복잡도는 $O(n \times m + p \times l)$입니다.
keymap을 순회하는 반복문 $O(n)$keys를 순회하는 반복문 $O(m)$unordered_map의 삽입 및 검색 $O(1)$targets를 순회하는 반복문 $O(p)$target문자열을 순회하는 반복문 $O(l)$- $O(n) \times O(m) + O(1) + O(p) \times O(l)$
- $O(n \times m) + (p \times l)$
공간 복잡도는 $O(n)$입니다.
minKeyPress는 최악의 경우 모든 알파벳 26개 $O(26) \approx O(1)$answer은targets의 크기만큼 할당 $O(n)$
테스트 1 〉 통과 (0.03ms, 4.14MB)
테스트 2 〉 통과 (0.03ms, 4.13MB)
테스트 3 〉 통과 (0.03ms, 4.02MB)
테스트 4 〉 통과 (0.03ms, 4.22MB)
테스트 5 〉 통과 (0.03ms, 4.11MB)
테스트 6 〉 통과 (0.04ms, 4.2MB)
테스트 7 〉 통과 (0.03ms, 3.61MB)
테스트 8 〉 통과 (0.03ms, 4.19MB)
테스트 9 〉 통과 (0.02ms, 4.12MB)
테스트 10 〉 통과 (0.03ms, 4.13MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 3.62MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.14ms, 4.2MB)
테스트 15 〉 통과 (0.16ms, 4.2MB)
테스트 16 〉 통과 (0.16ms, 4.23MB)
테스트 17 〉 통과 (0.24ms, 4.22MB)
테스트 18 〉 통과 (0.11ms, 4.19MB)
테스트 19 〉 통과 (0.14ms, 3.67MB)
테스트 20 〉 통과 (0.16ms, 4.14MB)
테스트 21 〉 통과 (0.15ms, 4.2MB)
테스트 22 〉 통과 (0.17ms, 4.21MB)
테스트 23 〉 통과 (0.15ms, 4.17MB)
댓글남기기