문제 태그

• 문자열
• 스택
• 정규형

한국어 문제 해석

문자열 A와 B가 주어진다. 문자열은 왼쪽 괄호, 문자 x, 오른쪽 괄호로만 이루어진다.

다음 두 연산을 원하는 만큼 수행할 수 있다.

• 부분 문자열 (xx)를 xx로 바꾼다.
• 부분 문자열 xx를 (xx)로 바꾼다.

A를 B와 같게 만들 수 있는지 판정한다.

문제 요약

• 두 연산은 서로 역연산 관계다.
• 결국 (xx)와 xx는 같은 덩어리로 취급할 수 있다.
• 두 문자열이 같은 정규형으로 줄어드는지 비교하면 된다.

예시 워크스루

첫 번째 예시에서 A는 (xx)x이고 B는 x(xx)다.

• A의 앞부분 (xx)를 xx로 줄이면 xxx가 된다.
• xxx의 뒤쪽 xx를 (xx)로 늘리면 x(xx)가 된다.