[algospot][QUADTREE] 쿼드 트리 뒤집기

문제 : https://www.algospot.com/judge/problem/read/QUADTREE

---

분할정복 문제.

 

만약 입력으로 받은 문자열의 길이가 1이라면 이는 압축이 되는 경우가 없을 때이다. (x가 입력에 없음)

이 때는 해당 문자열을 그대로 반환한다.

문자열 길이가 1이 아닌 경우는 첫 번째 문자가 반드시 x가 된다.

입력으로 받은 문자열을 앞에서부터 탐색하면서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분을 배열에 각각 저장한다. 

탐색 하면서 나올 수 있는 경우는 총 3가지이다.

탐색 중인 문자(now)가 

1. 'w'인 경우 : 배열에 "w" 저장 

2. 'b'인 경우 : 배열에 "b" 저장

3. 'x'인 경우 : 탐색 중인 인덱스부터 시작하는 문자열로 다시 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분을 배열로 만들어서 이를 상하 뒤집은 문자열을 저장. 

이를 배열 크기가 4가 될 때까지 반복 후 배열[2] + 배열[3] + 배열[0] +배열[1] 로 재조합한 문자열이 상하를 뒤집은 문자열이다.

 

빨간색 부분은 반복해서 나올 수 있는 부분이다. -> 함수로 뺀다.

함수의 반환 값은 (상하를 뒤집은 문자열, 문자열의 다음 인덱스)로 했다.

문자열의 다음 인덱스를 반환한 이유는 이를 반환해야 다음 탐색 인덱스를 알 수 있기 때문이다.

 

시간복잡도는 입력으로 받은 문자열을 탐색하면서 곧바로 뒤집은 문자열을 만들어내므로 문자열 길이가 N이라 했을 때, O(N).

---

소스코드 : https://gist.github.com/fpdjsns/f7a50d149950762f23f5e2109450be1a

[종만북보고 리팩토링] : https://gist.github.com/fpdjsns/8d177011a49b269f406a03f1b01160d5

---

기존에 문자열과 인덱스를 파라미터로 넘기고 다음 인덱스를 반환값으로 던졌는데 이를 반복자로 던지니까 쓸데없는 파라미터와 반환 값이 없어졌다. 자주 사용해야겠다. 쓸데없는 변수 선언 등이 없어져서 수행시간도 12ms -> 4ms 로 줄었다.

string solve(string::iterator& it) { // 반복자 파라미터
    char head = *it; // 가리키고 있는 문자 확인
    it++; // 다음 문자 확인
}

int main() {
    string s;

    // input.begin()은 const여서 별도의 변수에 한 번 담고 넘겨줬다.
    string::iterator it = input.begin(); 
    solve(it);
    return 0;
}