[Week 1] QUADTREE self review - Yunhyunjo

[Yunhyunjo]

QUADTREE self review

• 파일명: PQR/QUADTREE/Yunhyunjo.cpp
• 수행시간: 4ms

1. 고민 과정

재귀 호출을 통해 구현해야했기 때문에 base case와 어떤 값을 반환해야할 지를 고민했습니다.

2. 풀이 아이디어

분할 정복 문제로 스터디 자료에 있는 재귀함수 템플릿대로 구현하였습니다.

3. 작성한 코드와 설명

int i;
string s;

string quadtree() {

    if (s[i] != 'x') return ((s[i++] == 'b') ? "b" : "w");
    i++;
    string one = quadtree();
    string two = quadtree();
    string three = quadtree();
    string four = quadtree();

    return "x" + three + four + one + two;
}

quadtree()는 압출된 문자열을 뒤집어서 반환해주는 함수입니다.
입력받을 압축된 문자열 s와 인덱스를 i는 전역 변수로 선언해주었습니다.
4분할로 나누면서 압축하기 때문에 재귀호출을 4번 해주었고, 상하 반전을 시켜야하기 때문에 3 + 4 + 1 + 2로 return 시켜주었습니다.

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    while(n--) {
        i = 0;
        cin >> s;
        cout << quadtree() << "\n";
    }
}

문자열을 입력받고 결과를 출력하는 main함수로 매번 입력받을 때 i를 0으로 초기화 해주었습니다.