연관문제
[카카오 인턴] 키패드 누르기
문제
2020년 12월, 세 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 빠르게 ZOAC를 알리려 한다.
하지만 안타깝게도 성우는 독수리타법이다!
- 독수리 타법이란 양 손의 검지손가락만을 이용해 타자를 치는 타법이다.
- 성우는 한글 자음 쪽 자판은 왼손 검지손가락으로 입력하고, 한글 모음 쪽 자판은 오른손 검지손가락으로 입력한다.
- a의 좌표가 (x1, y1)이고, b의 좌표가 (x2, y2)일 때, a에 위치한 성우의 손가락이 b로 이동하는 데에는 a와 b의 택시 거리 |x1-x2|+|y1-y2| 만큼의 시간이 걸린다.
- 각 키를 누르는 데에는 1의 시간이 걸린다.
- 성우는 두 손을 동시에 움직일 수 없다.
- 성우가 사용하는 키보드는 쿼티식 키보드이며, 아래 그림처럼 생겼다.
바쁜 성우를 위하여 해당 문자열을 출력하는 데 걸리는 시간의 최솟값을 구해보자.
입력
첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다.
그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다. 빈 문자열은 주어지지 않는다.
출력
입력으로 주어진 문자열을 출력하는 데에 걸리는 시간의 최솟값을 출력한다.
예제
문제 정의
시뮬레이션 문제를 처음 풀어봤다. 재밌었다
문제에서 주어진 키보드를 재연해야 되는데, 2차원 배열에 모음/자음을 구별하는 int 값과, 알파벳 값을 pair로 저장했다. (모음은 0, 자음은 1)
모음/자음 여부를 구분하면 한글은 저장할 필요없다.
처음 왼손의 위치 좌표를 p1, 오른손의 위치 좌표를 p2에 저장했다.
그 후 반복문을 통해 주어진 문자열의 각 문자의 위치 좌표를 알아내고 자음/모음 여부, 위치 좌표를 tuple로 저장했다.
모음(0)인 경우 왼쪽 손의 위치좌표와 현재 문자좌표의 거리값을 계산하여 임시 변수에 저장하였고, 왼손의 위치좌표를 현재 문자좌표의 위치값으로 변경해주었다.
오른손도 마찬가지로 진행한 후 해당 이동횟수를 answer에 더한다.
[주석 없는 코드]
#include<bits/stdc++.h>
using namespace std;
char a, b, eng, kor;
string s;
int x, y, hand, tmp, answer;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// 모음: ㅏㅑㅓㅕ 자음: ㄱㄴㄷㄹ
vector<vector<pair<int, char>>> v;
v.push_back({
{0, 'q'}, {0, 'w'}, {0, 'e'}, {0, 'r'}, {0, 't'},
{1, 'y'}, {1, 'u'}, {1, 'i'}, {1, 'o'}, {1, 'p'}
});
v.push_back({
{0, 'a'}, {0, 's'}, {0, 'd'}, {0, 'f'}, {0, 'g'},
{1, 'h'}, {1, 'j'}, {1, 'k'}, {1, 'l'}
});
v.push_back({
{0, 'z'}, {0, 'x'}, {0, 'c'}, {0, 'v'},
{1, 'b'}, {1, 'n'}, {1, 'm'}
});
cin >> a >> b;
cin >> s;
pair<int, int> p1;
pair<int, int> p2;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
tie(hand, eng) = v[i][j];
if (eng == a) {
p1.first = i;
p1.second = j;
}
if (eng == b) {
p2.first = i;
p2.second = j;
}
}
}
for (char k : s) {
bool flag = false;
for (int i = 0; i < v.size(); i++)
{
tuple<int, int, int> fi;
for (int j = 0; j < v[i].size(); j++) {
tie(hand, eng) = v[i][j];
if (eng == k) {
fi = make_tuple(hand, i, j);
flag = true;
break;
}
}
if (flag) {
tmp = 0;
tie(hand, x, y) = fi;
if (hand == 0) {
tmp = abs(x - p1.first) + abs(y - p1.second) + 1;
p1.first = x;
p1.second = y;
}
else {
tmp = abs(x - p2.first) + abs(y - p2.second) + 1;
p2.first = x;
p2.second = y;
}
answer += tmp;
break;
}
}
}
cout << answer;
return 0;
}[주석 있는 코드]
#include<bits/stdc++.h>
using namespace std;
char a, b, eng, kor;
string s;
int x, y, hand, tmp, answer;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// 모음: ㅏㅑㅓㅕ 자음: ㄱㄴㄷㄹ
vector<vector<pair<int, char>>> v;
v.push_back({
{0, 'q'}, {0, 'w'}, {0, 'e'}, {0, 'r'}, {0, 't'},
{1, 'y'}, {1, 'u'}, {1, 'i'}, {1, 'o'}, {1, 'p'}
});
v.push_back({
{0, 'a'}, {0, 's'}, {0, 'd'}, {0, 'f'}, {0, 'g'},
{1, 'h'}, {1, 'j'}, {1, 'k'}, {1, 'l'}
});
v.push_back({
{0, 'z'}, {0, 'x'}, {0, 'c'}, {0, 'v'},
{1, 'b'}, {1, 'n'}, {1, 'm'}
});
cin >> a >> b;
cin >> s;
pair<int, int> p1;
pair<int, int> p2;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
tie(hand, eng) = v[i][j];
if (eng == a) {
p1.first = i;
p1.second = j;
}
if (eng == b) {
p2.first = i;
p2.second = j;
}
}
}
// cout << "p1 : " << p1.first << ", " << p1.second << "\n";
// cout << "p2 : " << p2.first << ", " << p2.second << "\n";
for (char k : s) {
bool flag = false;
for (int i = 0; i < v.size(); i++)
{
tuple<int, int, int> fi;
for (int j = 0; j < v[i].size(); j++) {
tie(hand, eng) = v[i][j];
if (eng == k) {
// cout << "Eng : " << eng << " k: " << k << "\n";
fi = make_tuple(hand, i, j);
flag = true;
break;
}
}
if (flag) {
tmp = 0;
tie(hand, x, y) = fi;
if (hand == 0) {
// cout << "(x, y) = " << x << "," << y << "\n";
// cout << "왼손 : p1 = " << p1.first << "," << p1.second << "\n";
tmp = abs(x - p1.first) + abs(y - p1.second) + 1;
p1.first = x;
p1.second = y;
}
else {
// cout << "(x, y) = " << x << "," << y << "\n";
// cout << "오른손 : p2 = " << p2.first << "," << p2.second << "\n";
tmp = abs(x - p2.first) + abs(y - p2.second) + 1;
p2.first = x;
p2.second = y;
}
// cout << tmp << " 번 누르기 ~~\n";
answer += tmp;
break;
}
}
}
cout << answer;
return 0;
}[지피티 코드]
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, pair<int, int>> pos = {
{'q',{0, 0}}, {'w', {0, 1}}, {'e', {0, 2}}, {'r', {0, 3}}, {'t', {0, 4}},
{'y', {0, 5}}, {'u', {0, 6}}, {'i', {0, 7}}, {'o', {0, 8}}, {'p', {0, 9}},
{'a', {1, 0}}, {'s', {1, 1}}, {'d', {1, 2}}, {'f', {1, 3}}, {'g', {1, 4}},
{'h', {1, 5}}, {'j', {1, 6}}, {'k', {1, 7}}, {'l', {1, 8}}, {'z', {2, 0}},
{'x', {2, 1}}, {'c', {2, 2}}, {'v', {2, 3}}, {'b', {2, 4}}, {'n', {2, 5}} ,{'m', {2, 6}}
};
char l, r;
string str;
int ans = 0;
bool isLeft(char c){
return string("qwertasdfgzxcv").find(c) != string::npos;
}
int getDist(pair<int, int> a, pair<int, int> b){
return abs(a.first-b.first) + abs(a.second-b.second);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> l >> r;
cin >> str;
pair<int, int> left = pos[l];
pair<int, int> right = pos[r];
for(char c : str){
pair<int, int> target = pos[c];
if(isLeft){
ans += getDist(left, target);
left = target;
}
else{
ans += getDist(right, target);
right = target;
}
ans++;
}
cout << ans;
}
