당신은 괄호 문자열을 입력하던 중 키보드에 접촉 불량이 있다는 사실을 알게 되었다. 이 키보드는 키를 한 번 누르면 해당 문자를 화면에 한 번 또는 두 번 연속으로 입력한다. 연속으로 몇 번 입력되었는지는 입력마다 달라질 수 있다. 누른 키의 문자가 입력되지 않거나 다른 문자로 바뀌는 일은 없다.
화면에 남은 괄호 문자열 가 주어진다. 원래 입력하려던 문자열, 즉 누른 키를 순서대로 한 글자씩 기록한 문자열이 올바른 괄호 문자열이었을 가능성이 있는지 판정하여라. 각 키 입력에서 중복이 발생했는지는 알 수 없으며 중복이 전혀 발생하지 않았을 수도 있다.
올바른 괄호 문자열은 다음과 같이 정의한다.
(와 )를 붙인 문자열도 올바른 괄호 문자열이다.첫째 줄에 화면에 남은 문자열의 길이 이 주어진다.
둘째 줄에 길이 인 괄호 문자열 가 주어진다.
원래 입력하려던 문자열이 올바른 괄호 문자열이었을 가능성이 있으면 YES, 없으면 NO를 출력한다.
(와 )만으로 이루어진다.첫 번째 예제에서는 원래 입력하려던 문자열이 ()이고, 첫 번째 키 입력에서만 괄호가 두 번 입력되었다면 화면에 (()가 남는다.
두 번째 예제에서는 여는 괄호 키를 정확히 한 번 눌렀지만, 닫는 괄호 키는 적어도 두 번 눌렀어야 한다. 따라서 원래 입력하려던 문자열이 올바른 괄호 문자열일 수 없다.
세 번째 예제에서는 화면에 남은 여는 괄호와 닫는 괄호의 개수가 같다. 그러나 첫 여는 괄호 다음에 나타나는 닫는 괄호 세 개를 입력하려면 닫는 괄호 키를 적어도 두 번 눌러야 하므로 올바른 괄호 문자열을 복구할 수 없다.