"abcdefgh" 1차원 배열이 있을 때, 3번째 원소를 기준으로 회전한다고 보자.
결과는 다음과 같다.
"defghabc"
알고리즘은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | #include <iostream>
#include <vector>
using namespace std;
void Reverse(vector<char>* data, int start, int end);
int main()
{
vector<char> chars;
chars.push_back('a');
chars.push_back('b');
chars.push_back('c');
chars.push_back('d');
chars.push_back('e');
chars.push_back('f');
chars.push_back('g');
chars.push_back('h');
int rotationPivot = 3;
Reverse(&chars, 0, chars.size() - 1);
Reverse(&chars, 0, chars.size() -1 - rotationPivot);
Reverse(&chars, chars.size() - rotationPivot, chars.size() - 1);
for each (auto var in chars)
{
cout << var;
}
cout << endl;
return 0;
}
void Reverse(vector<char>* data, int start, int end) {
int iter = (end - start + 1)/2;
int cnt = 0;
while (iter > cnt) {
char tmp = (*data)[start];
(*data)[start] = (*data)[end];
(*data)[end] = tmp;
start++;
end--;
cnt++;
}
} |
조금 더 개량한 버전은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | void Reverse(vector<int>* data, int start, int end);
vector<int> solution(vector<int> &A, int K) {
// write your code in C++14 (g++ 6.2.0)
Reverse(&A, 0, A.size());
Reverse(&A, 0, K);
Reverse(&A, K, A.size());
return A;
}
void Reverse(vector<int>* data, int start, int end) {
int iter = (end - start)/2;
int cnt = 0;
while (iter > cnt) {
int tmp = (*data)[start];
(*data)[start] = (*data)[end-1];
(*data)[end-1] = tmp;
start++;
end--;
cnt++;
}
}
|
댓글 없음:
댓글 쓰기