이 문제는 규모가 큰 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] << " "; } |
'개발 > 알고리즘 & 자료구조' 카테고리의 다른 글
| [C++] 문자열 뒤집기(Reverse String) 알고리즘 (0) | 2020.09.28 |
|---|---|
| [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체 (22) | 2013.09.29 |
| [C++] 두 정수 사이의 모든 합 구하기 (5) | 2013.09.21 |
| [JAVA] 소수 구하기 최적의 알고리즘 (1) (6) | 2013.09.20 |
| [JAVA] Insertion Sort (삽입정렬) (3) | 2013.07.28 |
| [JAVA] 재귀 - 이진트리(Binary Tree)의 순회 (6) | 2013.07.08 |