트리 복구 (백준 6597)

안녕하세요. 오늘은 트리를 복구할 거예요.

문제

https://www.acmicpc.net/problem/6597

아이디어

구간별로 나눕시다.
print(l1,r1,l2,r2)를 s에서 [l1,r1], s2에서 [l2,r2]까지를 볼때 출력을 하는 함수입니다.

당연하지만 s[l1]은 맨 마지막에 출력해야합니다.
또한 s2에서 s[l1]이 있는 위치를 기준으로 왼쪽을 먼저 print해주어야합니다.
그러므로 s2에서 s[l1]이 있는 인덱스를 i라고 하면 s2에서 [l2,i-1]까지를 print해주고 개수를 맞춰서 s에서 [l1+1,l1+i-l2]를 print해주면 됩니다. 똑같이 오른쪽도 print해주면 됩니다.

소스코드

#include <iostream>
#include <string>
#define ll long long
using namespace std;

string s, s2;
void print(int l1,int r1,int l2,int r2)
{
    if (l1 > r1 || l2 > r2) return;
    ll i;
    for (i = l2; i <= r2; i++)
        if (s2[i] == s[l1])
            break;

    print(l1 + 1, l1 + i - l2, l2, i - 1);
    print(l1 + i - l2 + 1, r1, i + 1, r2);
    cout << s[l1];
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    while (cin >> s >> s2)
    {
        print(0, s.length() - 1, 0, s2.length() - 1);
        cout << "\n";
    }
}

감사합니다.