문제
Albert는 QWERTY 키보드를 이용해 (위 그림 참고) 영문 대문자로 ('A'-'Z') 구성된 문자열을 입력하고 싶다. 아직 키보드 만지는 것이 서툰 Albert는 왼쪽 검지만을 이용해 버튼을 누르는 버릇이 있다.
각 버튼을 눌렀다 떼어서 글자 하나를 입력하는데 1초가 걸리고, 검지를 한 버튼에서 인접한 다른 버튼으로 옮기는데는 2초가 걸린다고 하자 (문자열을 입력하는 동안 손가락은 항상 키보드 버튼 위에서만 이동한다고 하자).
각 버튼의 주변에는 최대 6개의 인접한 버튼이 있을 수 있다. 가령, 검지를 S버튼에서 A, W, E, D, X, 혹은 Z로 옮기는 경우 2초가 걸린다.
Albert가 어떤 문자열을 입력하기 위해서는 먼저 왼쪽 검지를 해당 문자열의 첫 글자에 해당하는 버튼 위에 올린 후, 그 때 부터 시간을 측정한다.
만약 "QWERTY" 라는 문자열를 입력하려고 한다면, 아래와 같은 방법으로 16초만에 입력할 수 있다.
입력하기에 앞서 우선 왼쪽 검지를 Q버튼 위로 이동한다 (이에 걸리는 시간은 포함하지 않는다).
Q버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 1초)
W버튼으로 이동하는데 2초가 걸린다. (총 3초)
W버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 4초)
E버튼으로 이동하는데 2초가 걸린다. (총 6초)
E버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 7초)
R버튼으로 이동하는데 2초가 걸린다. (총 9초)
R버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 10초)
T버튼으로 이동하는데 2초가 걸린다. (총 12초)
T버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 13초)
Y버튼으로 이동하는데 2초가 걸린다. (총 15초)
Y버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 16초)
다른 예로, "LOM" 라는 문자열을 입력하려 한다면 9초가 걸린다.
L버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 1초)
O버튼으로 이동하는데 2초가 걸린다. (총 3초)
O버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 4초)
M버튼으로 이동하는데 4초가 걸린다 (O -> K -> M으로 이동하는 것이 제일 빠르다). (총 8초)
M버튼을 누르고 떼어서 입력하는데 1초가 걸린다. (총 9초)
입력으로 영문 대문자('A"-'Z')로만 구성된 문자열이 주어졌을 때, Albert가 가장 빨리 입력할 경우 몇 초나 필요한지 계산하는 프로그램을 작성하시오.
입력
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 걸쳐 영문 대문자로만 구성된 문자열이 (공백없이) 주어진다.
출력
각 테스트 케이스에 대하여 입력으로 주어진 문자열을 입력하는데 걸리는 최소 시간을 출력한다.
https://www.acmicpc.net/problem/20914
한마디로 코든 키보드값 사이의 거리를 구현하라는문제이다.
개 빢 구현문제이므로 아이디어만 보시고 자세한내용은 크게도움이 안될것이다.
풀이
아이디어 1. 키보드 자판 생김새만보고, 그 사이 키들의 관계를 구현한뒤에
나중에 키보드글자(대문자)와 매칭한다.
이와 같은 3x7 칸의 키보드자판을먼저 구현하고 오른쪽의 22, 23, 24, 25, 26 은 나중에 구현한다.
아이디어2. 3행인데 이것을 3층으로 보아
한층사이 간격을 먼저구현후 두층 간격을 나중에구현한다.
우선 같은층을 구현한 코드는 아래와 같다.
아직까진 할만하다.
아이디어3. 가장중요한 매과정마다 검산을 거쳐 다음단계가기전까지 완벽하게 오류를 잡는다. 아래는 keyboard[현재키][다음키] 를 출력하여 확인한다.
0으로 표기된곳은 현재키와 다음키가같은경우 이동비용은 0
아이디어4. 키보드배열을 보면 한층간의 관계에서는 우상단으로 가는 경우 거리가 2가아닌 1이다.
마찬가지로 좌하단으로 가는 거리도 1이다.
이또한 검산용 코드를 사용하여 확인하였다.
아이디어5. 두층간의 관계에서는 우상단으로 가는경우 같은 열부터 3개의 키값은 모두 거리가 2이다. 예로들어 15에서 1, 2, 3 키값은 모두 거리가 2이다. 그다음 4부터 3, 4, 5... 증가한다.
반대경우로 좌하단으로 가는경우도 같은 룰이다.
이또한 검산용코드를 사용했음.
마지막으로 22, 23, 24, 25, 26키는
이런식으로 구현했다.
가장중요한 입력받은 대문자하나하나 고유의 키값 1~26으로 바꿔주는 함수는 아래와 같다.
노가다 조금하면된다. 앞에서이미 많이해서 아프지않다.
아이디어6. 최종 검산용 코드로, 키보드배열대로 키입력을 직접받아서 이동비용을 전부 출력해주는 코드이다.
이런식으로 직접입력하여 수동적으로 확인가능하다.
색깔좀 입혀봤다.
아래는 전체코드이다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <Windows.h>
int keyboard[27][27] = {0}; //[preKEY][KEY] 이전키에서 현재키까지 이동 비용. 동일위치는 모두 0인 상태
//각각 키사이 거리(최소단위 2)를 모두 기록할것임.
void input(); //입력을 받는 부분
void makeKeyboard(); //키보드의 모든 키값 설정
int findKEY(char c); //문자하나를 고유 키값으로 변환
//모든키값 사이 이동 비용을 계산하는 함수
void makeKeyboard() {
//1 : 동일층의 모든 키값
for (int i = 1; i <= 3; i++) { //1, 2, 3층
for (int j = 7 * i - 6 ; j <= 7 * i; j++) { //현재 키값 j
for (int k = j; k <= 7 * i; k++) { //오른쪽방향의 키값 k
if (j - k != 0) { //동일위치가 아닌것만 기록
keyboard[j][k] = 2 * abs(k - j); //두키 사이거리(단위 2)기록
}
}
for (int k = j; 7 * i - 6 <= k; k--) { //왼쪽방향 키값 k
if (j - k != 0) { //동일위치가 아닌것만
keyboard[j][k] = 2 * abs(k - j); //두키 사이거리(단위 2)기록
}
}
}
}
//2 : 한층아래의 모든 키값
// 1층 : 1~7
// 2층 : 8~14
// 3층 : 15~21
for (int i = 1; i <= 3; i++) { //세개의 층을살핀다
for (int j = 7 * i - 6; j <= 7 * i; j++) { //1~7 8~14 15~21
if (i + 1 <= 3) { //유효한 아래층일때만
//우하단
for (int k = j + 7; k <= 7 * (i + 1); k++) {
if (7 * i + 1 <= k && k <= 7 * (i + 1)) //여기는 필요없지만 혹여나 오류방지를 위하여
keyboard[j][k] = 2 * (k - j - 6); //우하단은 이동비용이 바로밑 1로시작하여 1씩증가. 한층의차이가 7임을 감안
}
//좌하단
for (int k = j + 7 - 1; 7 * (i + 1) - 6 <= k; k--) { //바로밑은제외, 바로밑에서 왼쪽부터 시작하여 줄여나감
if (7 * i + 1 <= k && k <= 7 * (i + 1)) //!!!!!! k가 층을벗어남을 방지. 중요함!!!!!!!!!!
keyboard[j][k] = 2 * abs(k - j - 7); //좌하단은 바로밑의 왼쪽키도 비용이 2임을 고려
}
}
if (i - 1 >= 1) { //유효한 윗층층일때만
//우상단
for (int k = j - 7; k <= 7 * (i - 1); k++) {
if (7 * (i - 1) - 6 <= k && k <= 7 * i)
keyboard[j][k] = 2 * abs(k - j + 7); //우하단은 이동비용이 바로밑 1로시작하여 1씩증가. 한층의차이가 7임을 감안
}
//좌상단
for (int k = j - 7 - 1; 7 * (i - 1) - 6 <= k; k--) { //바로밑은제외, 바로밑에서 왼쪽부터 시작하여 줄여나감
if (7 * (i - 1) - 6 <= k && k <= 7 * i) //k가 해당 층을 벗어나면 예외 처리 중요한코드
keyboard[j][k] = 2 * abs(k - j + 6); //좌하단은 바로밑의 왼쪽키도 비용이 2임을 고려
}
}
if (8 <= j && j <= 21)
keyboard[j][j - 7] = 2;
}
}
//검산 - 아래층확인용
//for (int i = 1; i <= 3; i++) {
// for (int j = 7 * i - 6; j <= 7 * i; j++) { //i층
// printf("%2d >> ", j);
// for (int k = 7 * (i+1) - 6; k <= 7 * (i+1); k++) { //(i+1)층 아래층
// if(1 <= i+1 || i+1 <= 3) //유효한것만
// printf("%2d ", keyboard[j][k]);
// }
// printf("\n");
// }
// printf("\n");
//}
//검산 - 윗층확인용
//for (int i = 1; i <= 3; i++) {
// for (int j = 7 * i - 6; j <= 7 * i; j++) { //i층
// printf("%2d >> ", j);
// for (int k = 7 * (i - 1) - 6; k <= 7 * (i - 1); k++) { //(i-1)층 위층
// if (1 <= i - 1 || i - 1 <= 3) //유효한것만
// printf("%2d ", keyboard[j][k]);
// }
// printf("\n");
// }
// printf("\n");
//}
//3 : 두층아래의 모든 키값
// 1층 : 1~7
// 2층 : 8~14
// 3층 : 15~21
for (int j = 1; j <= 7; j++) {
//우하단
for (int k = j + 14; k <= 21 ; k++) {
if (15 <= k && k <= 21)
keyboard[j][k] = 2 * (k - j - 12); //우하단은 이동비용이 바로밑 1로시작하여 1씩증가. 한층의차이가 7임을 감안
}
//좌하단
for (int k = j + 14 - 2; 15 <= k; k--) { //바로밑은제외, 바로밑에서 왼쪽부터 시작하여 줄여나감
if(15 <= k && k <= 21)
keyboard[j][k] = 2 * abs(14 - k + j); //좌하단은 바로밑의 왼쪽키도 비용이 2임을 고려
}
if (j != 1) {
keyboard[j][14 + j - 1] = 4;
}
}
for (int j = 15; j <= 21; j++) {
//우상단
for (int k = j - 14; k <= 7; k++) {
if (1 <= k && k <= 7)
keyboard[j][k] = 2 * (k - j + 14); //우하단은 이동비용이 바로밑 1로시작하여 1씩증가. 한층의차이가 7임을 감안
}
//좌상단
for (int k = j - 14; 1 <= k; k--) { //바로밑은제외, 바로밑에서 왼쪽부터 시작하여 줄여나감
if (1 <= k && k <= 7)
keyboard[j][k] = 2 * (j - k - 12); //좌하단은 바로밑의 왼쪽키도 비용이 2임을 고려
}
if (j != 21)
keyboard[j][j - 13] = 4;
}
//검산 - 아래층확인용
//for (int j = 1; j <= 7; j++) { //i층
// printf("%2d >> ", j);
// for (int k = 15; k <= 21; k++) { //층 아래층
// printf("%2d ", keyboard[j][k]);
// }
// printf("\n");
//}
//검산 - 윗층확인용
//for (int j = 15; j <= 21; j++) { //i층
// printf("%2d >> ", j);
// for (int k = 1; k <= 7; k++) { //(i-1)층 위층
// printf("%2d ", keyboard[j][k]);
// }
// printf("\n");
//}
//4 : 기존키에 나머지 5개 키(22 23 24 25 26) 연결
for (int j = 1; j <= 7; j++) {
keyboard[j][22] = 2 * (8 - j);
keyboard[j][23] = 2 * (9 - j);
keyboard[j][24] = 2 * (10 - j);
keyboard[j][25] = 2 * (9 - j);
keyboard[j][26] = 2 * (10 - j);
}
for (int j = 8; j <= 14; j++) {
keyboard[j][22] = 2 * (7 + 8 - j);
keyboard[j][23] = 2 * (7 + 9 - j);
keyboard[j][24] = 2 * (7 + 10 - j);
keyboard[j][25] = 2 * (7 + 8 - j);
keyboard[j][26] = 2 * (7 + 9 - j);
}for (int j = 15; j <= 21; j++) {
keyboard[j][22] = 2 * (7 * 2 + 8 - j);
keyboard[j][23] = 2 * (7 * 2 + 9 - j);
keyboard[j][24] = 2 * (7 * 2 + 10 - j);
keyboard[j][25] = 2 * (7 * 2 + 8 - j);
keyboard[j][26] = 2 * (7 * 2 + 9 - j);
}
keyboard[21][22] = 4; //오류 수정용
//5 : 22 23 24 25 26 키에 기존키를 연결
for (int j = 7; j >= 1; j--) {
keyboard[22][j] = 2 * (8 - j);
keyboard[23][j] = 2 * (9 - j);
keyboard[24][j] = 2 * (10 - j);
keyboard[25][j] = 2 * (9 - j);
keyboard[26][j] = 2 * (10 - j);
}
for (int j = 14; j >= 8; j--) {
keyboard[22][j] = 2 * (7 + 8 - j);
keyboard[23][j] = 2 * (7 + 9 - j);
keyboard[24][j] = 2 * (7 + 10 - j);
keyboard[25][j] = 2 * (7 + 8 - j);
keyboard[26][j] = 2 * (7 + 9 - j);
}
for (int j = 21; j >= 15; j--) {
keyboard[22][j] = 2 * (7 * 2 + 8 - j);
keyboard[23][j] = 2 * (7 * 2 + 9 - j);
keyboard[24][j] = 2 * (7 * 2 + 10 - j);
keyboard[25][j] = 2 * (7 * 2 + 8 - j);
keyboard[26][j] = 2 * (7 * 2 + 9 - j);
}
keyboard[22][21] = 4; //오류 수정용
//6 : 22 23 24 25 26 키값간 연결
keyboard[22][23] = 2; keyboard[23][22] = 2;
keyboard[22][24] = 4; keyboard[24][22] = 4;
keyboard[22][25] = 2; keyboard[25][22] = 2;
keyboard[22][26] = 4; keyboard[26][22] = 4;
keyboard[23][24] = 2; keyboard[24][23] = 2;
keyboard[23][25] = 2; keyboard[25][23] = 2;
keyboard[23][26] = 2; keyboard[26][23] = 2;
keyboard[24][25] = 4; keyboard[25][24] = 4;
keyboard[24][26] = 2; keyboard[26][24] = 2;
keyboard[25][26] = 2; keyboard[26][25] = 2;
}
//입력받은 문자를 고유숫자인 키값으로 변경하는 함수
int findKEY(char c) {
int res = -1;
switch (c) {
case 'A': res = 8; break; case 'B': res = 19; break;
case 'C': res = 17; break; case 'D': res = 10; break;
case 'E': res = 3; break; case 'F': res = 11; break;
case 'G': res = 12; break; case 'H': res = 13; break;
case 'I': res = 22; break; case 'J': res = 14; break;
case 'K': res = 25; break; case 'L': res = 26; break;
case 'M': res = 21; break; case 'N': res = 20; break;
case 'O': res = 23; break; case 'P': res = 24; break;
case 'Q': res = 1; break; case 'R': res = 4; break;
case 'S': res = 9; break; case 'T': res = 5; break;
case 'U': res = 7; break; case 'V': res = 18; break;
case 'W': res = 2; break; case 'X': res = 16; break;
case 'Y': res = 6; break; case 'Z': res = 15; break;
}
return res;
}
//입력을 받고 출력을 하는 함수
void input() {
int n;
scanf("%d", &n);
while (n--) {
char in[101]; //입력받은 문자
scanf("%s", &in);
int size = 0; //입력받은 문자열 크기
int preKEY = -1;
int res = 0;
for (int i = 0; i < 101; i++) {
if (in[i] == '\0') //끝을 만나면 종료
break;
size++;
int KEY = findKEY(in[i]); //입력받은 문자를 고유 키값으로 변환
if (i == 0) { //처음에는 손가락이 시작하는 위치로 비용발생X
preKEY = KEY;
continue;
}
else {
res += keyboard[preKEY][KEY]; //이전키에서 현재키까지 비용을 추가
//printf("%2d => %2d 비용:%2d\n", preKEY, KEY, keyboard[preKEY][KEY]);
preKEY = KEY; //이전키 갱신
}
}
res += size; //키를 누를때마다 1초가 걸리므로 문자열길이만큼 추가하면 쉽게계산
printf("%d\n", res);
}
}
//검산용 출력 함수
void ex_input() {
while (true) {
int c;
scanf("%d", &c);
printf("======================================================================\n");
for (int i = 0; i <= 2; i++) {
if (i == 1)
printf(" ");
if (i == 2)
printf(" ");
for (int j = 1; j <= 7; j++) {
if (c == 7 * i + j) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][7 * i + j]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][7 * i + j]);
}
}
if (i == 0) {
if (c == 22) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][22]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][22]);
}
if (c == 23) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][23]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][23]);
}
if (c == 24) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][24]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][24]);
}
}
else if (i == 1) {
if (c == 25) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][25]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][25]);
}
if (c == 26) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
printf("%2d ", keyboard[c][26]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
else {
printf("%2d ", keyboard[c][26]);
}
}
printf("\n");
}
printf("======================================================================\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
}
}
int main(void) {
makeKeyboard();
ex_input(); //검산용
//input();
return 0;
}