일반화된 독일어 인용
면접 대비시간 제한3초메모리 제한512 MB
<<와 >>로만 이루어진 문자열이 독일식 또는 역방향 인용 부호의 올바른 짝을 이루는지 판정하고 각 기호를 여는 [ 또는 닫는 ]로 바꿔 출력하며 불가능하면 Keine Loesung을 출력합니다.
문제
독일어는 ‘«’와 ‘»’ 모양의 꺾쇠 인용 부호를 사용하므로 «전통적인» 방식으로 인용할 수 있다. 독일어에서 비전통적인 점은 »뒤집힌« 방식으로도 인용할 수 있다는 것이다. 실생활에서는 이 두 방식이 섞이지 않는데, 서로 다른 독일어권 국가에서 쓰이기 때문이다. 그런데 재미를 좀 내 보자. 이 두 인쇄 전통을 합치고 중첩 인용에 관한 규칙을 잊으면(즉 무한한 중첩을 허용하면), 다음과 같은 작은 인용 걸작을 쓸 수 있는 일반화된 독일어 규칙을 얻게 된다.
«»Anf¨uhrungszeichen« means «quote marks» in German»
비공식적으로, 어떤 문자열에서 인용 부호가 아닌 문자를 모두 제거했을 때 올바르게 구성된 일반화된 독일어 텍스트가 나오면 그 문자열을 올바른 인용이라고 하자. 형식적으로는 다음과 같다.
⟨G⟩ ::= ε | ⟨G⟩⟨G⟩ | ‘«’⟨G⟩‘»’ | ‘»’⟨G⟩‘«’
따라서 올바른 인용은 빈 문자열이거나, 두 올바른 인용을 이어 붙인 것이거나, 올바른 인용을 전통적 또는 뒤집힌 방식으로 인용한 것이다. 뒤의 두 경우에서 ⟨G⟩ 왼쪽의 인용 부호를 시작 인용, ⟨G⟩ 오른쪽의 인용 부호를 끝 인용이라고 한다. 예를 들어 인용 문자열 ‘«»’에서 인용 부호 ‘«’는 시작 인용이고, 문자열 ‘»«’에서 같은 인용 부호 ‘«’는 끝 인용이다.
주어진 문자열이 올바른 인용인지 판별하고, 맞다면 그 구조를 복원해야 한다. 즉 모든 시작 인용 부호를 ‘[’로, 모든 끝 인용 부호를 ‘]’로 바꾼다.
입력
첫 번째 줄이자 유일한 줄에 인용 부호들이 나열된 문자열이 하나 주어진다. ASCII 문자만 쓰기 위해 인용 부호 ‘«’와 ‘»’는 각각 ‘<<’와 ‘>>’로 인코딩된다. 문자열에는 다른 문자가 들어 있지 않다. 문자열은 비어 있지 않고 길이가 254자를 넘지 않는다.
출력
입력 문자열이 올바른 인용이면 모든 시작 인용 부호를 ‘[’로, 모든 끝 인용 부호를 ‘]’로 바꾼 결과를 출력한다. 가능한 해가 여러 개면 아무거나 하나 출력한다.
문자열이 올바른 인용이 아니면 “Keine Loesung”을 출력한다.