ACM 문제중 WERTYU

ACM 문제 중 하나. WERTYU를 풀어보았다. 

---

Description

 
A common typing error is to place the hands on the keyboard one row to the right of the correct position. So "Q" is typed as "W" and "J" is typed as "K" and so on. You are to decode a message typed in this manner.

Input

Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input.

Output

You are to replace each letter or punctuation symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output. 

Sample Input

O S, GOMR YPFSU/

Sample Output

I AM FINE TODAY.

---

문제는 다음과 같다. 쉽게 생각하면 키보드 좌판을 하나씩 밀면된다. W는 Q로 S는 A로. 

단 Q,A,Z같은 키는 나오지 않는 것으로 가정한다. 

처음 이 문제를 보고 어떻게 풀어야 할까 고민했다. 

왠만한 ACM문제가 코드의 길이라 그렇게 긴 경우는 잘 없다. (있는 경우도 종종있다.) 

우선, 나는 이 문제를 배열로 생각해 풀었다. 

그전에 따져봐야 하는 것이 input으로 들어오는 키들의 종류다. 알파벳은 기본적으로 들어올 것이다. 그리고 ';' 와 같은 키들도 들어온다. 여기서 한번 실수를 했던 점이 숫자를 고려하지 않았었다. 숫자도 당연히 들어올거란걸 고려 못하고 짰다가 다중에 디버깅하면서 고쳤다. 

이 문제를 풀 때 가장 중요한 포인트는 문자열에 관해서 얼마나 알고, 문자열과 관련된 함수들을 얼마나 알고있느냐에 따라 많이 달라진다. 

단순하게 짜는 경우도 있다. 들어오는 키값 마다 비교를 해서 그에 해당하는 키로 변환시키면 된다. 허나 그렇게 풀어서 무슨 의미가 있으랴. 

나는 이 문제를 3가지 키들의 타입으로 분류했다. 알파벳, 숫자, 남는 문자들 이렇게 나눈 뒤 입력 받은 값을 3경우로 검사하여 해당하는(입력된 값과 연결된 다른 값)값으로 바꿨다. 

위에서도 말했듯이 이 문제를 나는 배열을 이용해 짰다. 배열에 해당하는 키의 위치를 넣어두어 index로 접근했다. 

char sWords[][11] = { '[', ']', '\\', ';' , '\'', ',' , '.', '/', '`', '-', '=', 

 'P', '[', ']' , 'L', ';' , 'M' , ',' , '.', '`', '0', '-' };

char alpha[26] = {'A', 'V', 'X', 'S', 'W', 'D', 'F', 'G', 'U', 'H', 'J', 'K', 'N', 'B', 'I', 'O', 'Q', 'E', 'A', 'R', 'Y', 'C', 'Q',

'Z', 'T', 'Z'};

char num[10] = {'9','`', '1', '2', '3', '4', '5', '6', '7', '8'};

이렇게 우선 3가지 각각의 배열을 만들어 둔다. 간력히 설명하자면, sWords란, 이차원 배열로 이루어져있는데

[	]	\	;	'	,	.	/	`	-
P	[	]	L	;	M	,	.	0	-

위의 표와 같은 구성이다. 즉 '[ ' 키가 오면 아래 'P'값으로 출력해주면된다.  

alpha,num배열 또한 같은 구성이다. 이 배열들은 위의 문자와 같은 비교를 해줄 필요가 없다.

입력받은 값으로 index계산이 가능하므로 비교하기 위해 2차원 배열을 만들 필요는 없다. 

배열의 구성은 위 표와 같이 'B' 라는 값이 오면 'V'를 출력하면 된다. 

이제 이 배열들을 어떻게 이용할까. 

string sentence; // 문장을 입력받는다.

getline(cin, sentence); 

우선 가장 먼저 해야 할건 입력을 받는 일이다. 이는 위의 getline함수로 받는다. 

후에 string으로 받은 문자열을 c 스타일로 고쳐주어야 한다. 그 이유는 string의 경우 sentence[0] = "a"; 로 값을 바꿀수없다. 

기본적으로 제공하는 string class의 함수중에 replace라는 함수가 있지만 다른 방법을 이용했다. 

※물론 처음부터 char* sentence; 로 만들고 gets()함수로 받아도 상관은 없다.

string 문자열은 기본적으론 c++에서 제공하는 class다. 우선 이를 C style인 char*형으로 고쳐주어야한다. 

다행이도 이걸 제공해주는 기본 함수가 있다. c_str()함수다. sentence.c_str()을 하면 C style로 바뀐다. 

그러나 또 문제가 있다. 이렇게 변환해서 보니 string이 const char*이다. 아마 내 블로그에 올린 글을 열심히 본 사람이라면 쉽게 해법을 찾겠지만 보통은 잘 모르는 경우가 많다. C++에서는 여러가지 형변환이 존재한다. 이 내용은 C++내용에 있으므로 생략. 

여하튼 const를 떼는 방법은 const_cast를 사용하면된다. 

const_cast<char*>(sentence.c_str()); 

과 같이 할 경우 sentence를 char*형과 같이 사용 할 수 있다.

이제 문제는 거의 다 푼 거나 마찬가지다.

아, 한가지 문제점이 더 남았다. 어떻게 문자를 알파벳과, 숫자, 그외문제로 구분 할 것인가. "전부 비교해야하는거 아닌가?" 의문이 들겠지만, 기본적으로 제공해 주는 함수가 있다. isalpha(), isdigit()과 같은 함수들이다. 이는 기본적으로 있는 표준함수들이다. 

for(int i = 0; i < sentence.length(); i++) { 

if(isalpha(sentence[i])) { 

sentence[i] = alpha[sentence[i]-'A'];

}//end of if

else if(isdigit(sentence[i])) {

sentence[i] = num[sentence[i]-'0'];

}//end of else if 

else {

for(int j = 0; j < 11; j++) {

if(sWords[0][j] == sentence[i]){

sentence[i] = sWords[1][j];

break;

}//end of if

}//end of for(int j)

}//end of else

}//end of for(int i)

 

위와 같은 코드로 구성하면 간단하게 받은 값을 비교 할 수 있다. 간단한 코드이므로 설명은 생략! 

이로써 문제를 다 풀었다. 이제 ACM문제 검사 페이지에서 검사를 하면 된다. 여기서 더 추가 해주어야 하는건 

ACM 문제 검사일 경우 while문으로 반복을 해줘야하고 무한 루프에 빠지면 안된다. 

그래서 전체 코드는 

string sentence; // 문장을 입력받는다.

while(true) { 

getline(cin, sentence); 

if(sentence.empty()) break;

const_cast<char*>(sentence.c_str()); // string -> char*

for(int i = 0; i < sentence.length(); i++) { 

if(isalpha(sentence[i])) { 

sentence[i] = alpha[sentence[i]-'A'];

}//end of if

else if(isdigit(sentence[i])) {

sentence[i] = num[sentence[i]-'0'];

}//end of else if 

else {

for(int j = 0; j < 11; j++) {

if(sWords[0][j] == sentence[i]){

sentence[i] = sWords[1][j];

break;

}//end of if

}//end of for(int j)

}//end of else

}//end of for(int i)

cout << sentence << endl;

}//end of while

와 같이 바꿔 주어야한다.  포인트는 while문을 탈출하기 위해 반드시 어떤 조건으로 탈출시켜야 하는 것이다. 아니면 time limit이 걸린다. 

결과는 위와 같다. 잘된다.