DNA 조작기

브루스 배너는 헐크의 몸무게가 조금 늘었다는 사실을 알아차렸다. 다른 어벤저스는 그를 놀리며 '인크레더블 벌크'라고 부른다. 브루스의 영양사는 헐크에게 야외에서 더 운동하고 엑스박스 하는 시간을 줄이라고 권한다. (그럴 리가 없지만.) 대신 브루스는 헐크의 느려진 신진대사를 끌어올리려고 DNA 치료를 선택한다.

자원이 풍부한 배너는 오래된 DNA 접합 기계를 찾았다. 이 기계는 DNA 문자열에 제한된 변경을 일으키도록 프로그래밍할 수 있다. 이런 변경을 생성 규칙이라고 한다. 당신의 일은 브루스가 체중 감량 프로그램에 필요한 복잡한 DNA 문자열을 만들 수 있는지 판단하도록 돕는 것이다.

생성 규칙은 $a \to bc$ 형태이며, $a$, $b$, $c$는 각각 문자다. 생성 체계는 생성 규칙의 모음이다. 예를 들어 다음은 하나의 생성 체계다.

• 규칙 0: A → GC
• 규칙 1: A → AA
• 규칙 2: G → TA

이 생성 체계가 주어졌을 때, 어떤 문자열이 시작 기호에서 생성될 수 있는지 알고 싶다. 예를 들어 위 체계에서 'A'로부터 'TAGCC'를 생성할 수 있는가? 답은 YES이며, 유도 과정은 아래와 같다.

1. A ⇒ GC (위치 0의 A에 규칙 0 적용)
2. GC ⇒ TAC (위치 0의 G에 규칙 2 적용)
3. TAC ⇒ TAAC (위치 1의 A에 규칙 1 적용)
4. TAAC ⇒ TAGCC (위치 2의 두 번째 A에 규칙 0 적용)

유도의 각 단계는 적용할 규칙 번호와 적용할 위치, 두 수로 나타낼 수 있다. 모든 인덱스는 0부터 시작한다.

생성 체계 $P$, 시작 기호 $s$, 목표 문자열 $t$가 주어졌을 때, 생성 규칙을 적용해 $s$에서 $t$를 생성할 수 있는지 판단하는 프로그램을 작성하라. 가능하면 유도 과정을 반환한다. $m$단계로 이루어진 유도는 각 치환의 규칙 번호와 위치를 담은 $2m$개의 정수 목록으로 주어진다. 예를 들어 위의 4단계 유도는 8개 원소 목록 <0, 0, 2, 0, 1, 1, 0, 2>로 나타낼 수 있다.

$s$에서 $t$를 유도할 수 없으면 빈 유도 목록을 반환해야 한다. 또한 $s = t$라서 자명한 유도가 존재하면 빈 유도를 반환해야 한다. 일반적으로 가능한 유도는 여러 개일 수 있다. 프로그램은 그중 하나의 올바른 유도를 반환해도 된다.

입력 파일은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 생성 체계와 이어지는 여러 개의 시작 기호/목표 문자열 쌍으로 구성된다. 각 생성 규칙은 새 줄에 주어지고, 한 줄에 '$'만 있는 줄로 생성 체계가 끝난다. 이어서 시작 기호/목표 문자열 쌍이 여러 개 주어지며, 한 줄에 '#'만 있는 줄로 끝난다. 생성 규칙에 쓰이는 기호는 알파벳 문자 또는 밑줄 문자(_)일 수 있다. 범위는 'a'부터 'z', 'A'부터 'Z'이다.

모든 입력과 출력을 처리하는 프로그램은 우리가 제공한다. 당신은 다음 프로시저의 본문만 작성하면 된다.

private static ArrayList<Integer> computeDerivation(
  ArrayList<Character> lhs, // 생성 규칙의 왼쪽 변
  ArrayList<String> rhs, // 대응하는 오른쪽 변
  Character start, // 시작 기호
  String target) // 목표 문자열

• 문자 배열 lhs: lhs[i]에는 i번째 규칙의 왼쪽 변이 들어 있다.
• 문자열 배열 rhs: rhs[i]에는 i번째 규칙의 오른쪽 변이 들어 있다.
• 문자 start: 시작 기호다.
• 문자열 target: 목표 문자열이다.

이 프로시저는 위에서 설명한 유도를 담은 정수 ArrayList를 반환한다. 우리 프로그램은 당신의 유도가 올바른지 확인하고, 올바르면 그에 맞는 출력을 생성한다. 유도가 올바르지 않으면(예: 규칙을 잘못 적용한 경우) 오류 메시지를 낸다.