[C++] 문자열 뒤집기(Reverse String) 알고리즘

이 문제는 규모가 큰 IT회사에서 단골 문제로 나온다.

간단히 풀 수 있는 문제여서 면접 중에 화이트보드로 풀라고 하는 경우가 많다.

 

이 문제의 핵심은 결과만 나오는 것이 아니라

복잡도를 최소한으로 해서 결과가 나오게 하는 것이다.

 

 

 

1. 문제

char arr[6] = { 'S', 'T', 'R', 'I', 'N', 'G' };
char result[6] = {0,};

 

주어진 arr 문자 배열의 내용을 역순으로 result 배열에 담아야 한다.

결과 배열 char result[6]에는 'G', 'N', 'I', 'R', 'T', 'S' 순으로 들어있도록 만들면 된다.

 

 

2. 어떻게 풀까? (알고리즘)

 

직관적인 방법으로는 result 배열의 끝 인덱스부터 하나씩 역순으로 접근해서

result 배열에 차례대로 넣는 것이 있다.

 

arr의 마지막 인덱스를 result의 첫 번째 인덱스에

arr의 4번째 인덱스를 result의 두 번째 인덱스에...

 

 

3. 코드

for (int i = 0; i < sizeof(arr); i++) {
     result[i] = arr[sizeof(arr) - i - 1];   // 배열이 0부터 시작하므로 -1을 해줌
 }

 // 출력
 for (int i = 0; i < sizeof(result); i++) {
     cout << result[i] << " ";
 }

결과>>

G N I R T S

주어진 문자 배열의 길이만큼 loop가 돌게된다.

이 정도로는 면접관들이 만족하지 않는다.ㅎㅎㅎ

 

 

 

 

loop를 더 짧게 도는 방법은?????

 

 

 

 

위와 같이 양 끝쪽을 서로 맞바꾸어 주다보면 문자열이 역순으로 바뀌게 된다.

만약 주어진 문자배열이 홀수개여도 같은 규칙이 적용된다. (가운데 값은 남게 된다.)

 

이 알고리즘으로 코드를 짜면 loop 도는 횟수가 반으로 줄어든다!

 

 

코드

memcpy(result, arr, sizeof(arr));    // arr 배열을 result 배열에 복사
 for (int i = 0; i < sizeof(result) / 2; i++) {        // result 배열의 반만 돌아도 된다
     // swap
     int temp = result[i];
     result[i] = result[sizeof(result) - 1 - i];    // 배열이 0부터 시작하므로 -1을 해줌
     result[sizeof(result) - 1 - i] = temp;
 }

 // 출력
 for (int i = 0; i < sizeof(result); i++) {
     cout << result[i] << " ";
 }​