Magicka timer 1s memory - MB

Magicka™은 Arrowhead Game Studios에서 개발한 액션 어드벤쳐 게임이다. Magicka에서 당신은 마법사로 플레이를 하게 될 경우, 마법 주문을 수행하기 위해서 원소를 부르거나 조합하게 된다. 본 문제는 위의 방식과 유사하나, 당신이 Magicka 게임을 해본적이 없다고 가정한다.

마법사로서 당신은 8개의 "기본" 원소를 부를 수 있다. 각 원소는 하나의 영문 대문자로 표현되며 이는 다음과 같다. {Q, W, E, R, A, S, D, F}

당신이 원소를 부르게 되면, 이는 원소 리스트에 추가 된다. 예를 들어 W를 부르고 A를 부르면( 다음 부터는 "WA를 부름" 이라고 표현) 원소 리스트는 [W, A]가 되며, 이경우 원소를 부르는 순서에 따른 원소 리스트를 적으면 다음과 같다.

두개의 "기본" 원소는 다른 "비 기본" 원소로 바뀔 수 있다. "비 기본" 원소는 "기본" 원소를 제외한 나머지 알파벳 문자가 된다.

예를 들어 "기본" 원소 Q와 F는 "비 기본" 원소 T로 합쳐진다. 합쳐지는 경우는 서로 인접해 있는 경우에만 가능하다. 만약 원소 리스트 맨 뒤의 2개의 원소가 "비 기본" 원소로 합쳐질 수 있을 경우에는 2개의 원소는 원소 리스트에서 사라지고, 이에 대응되는 "비 기본" 원소로 합쳐지게 된다. Q와 F가 T로 합쳐지는 예를 들면 원소 리스트가 [A, Q, F] 혹은 [A, F, Q] 일 경우 맨 뒤에 Q와 F가 T로 합쳐질 수 있으므로 결과적으로 [A, T] 가 된다.

다음으로 "기본" 원소간의 쌍이 서로 상쇄 되는 경우가 있다. 만약 상쇄되는 원소 2개가 원소 리스트에 존재하고, 그 원소들 모두 다른 원소와 합쳐지지 않을 경우, 원소 리스트는 상쇄가 발생하여, 원소 리스트는 비워지게 된다.

이러한 것은 입력 순서대로 이루어지며 두 가지 조건이 서로 겹치는 경우 합쳐지는 것이 우선이다. 또한 합쳐지는 것은 서로 인접한 경우에만 가능하다.

예를 들어, Q와 F가 T로 합쳐지고, Q과 F는 서로를 상쇄한다 하자. 이럴 경우 여러개의 예시를 들면 다음과 같은 결과가 나온다.

● QF → [Q] → [Q, F] → [T] (Q와 F가 T로 합쳐진다. 입력 순서대로 하되 조건이 겹칠 경우 합쳐지는것이 우선이다.) ● QEF → [Q] → [Q, E] → [Q, E, F] → [] (Q와 F가 상쇄를 발생시키기 때문에, F가 불려지는 순간 원소 리스트가 비워지게 된다 ● FQE → [Q] → [Q, F] → [T] → [T, E] (F와 Q가 T로 합쳐지고, 그 다음 E가 불러진다) ● RFQ → [R] → [R, F] → [R, F, Q] → [R, T] (F 와 Q가 T로 합쳐지게 된다.) ● QQF → [Q] → [Q, Q] → [Q, Q, F] → [Q, T] (두 번째 Q와 F가 T로 합쳐지게 되어, 첫 번째 Q와 F로 인한 상쇄가 발생되지 않게 된다) ● FAFBQ → [F] → [F, A] → [F, A, F] → [F, A, F, A] → [F, A, F, A, Q] → [] (첫 F와 Q가 상쇄를 발생시켜 원소리스트를 비워버린다. )

부르게 되는 원소들이 주어졌을 때, 이를 모두 부르게 될 경우 최종적으로 원소 리스트에 남는 원소들은 무엇인지 찾는 프로그램을 작성하라.