균형 잡힌 소떡소떡
면접 대비시간 제한1초메모리 제한512 MB
왼쪽 끝에서만 문자를 지워서 s와 t의 개수가 같은 가장 긴 문자열을 만드는 문제입니다.
문제
소떡소떡은 기다란 꼬치에 소세지와 떡을 끼운 음식이다. 편의상 소떡소떡을 알파벳 s와 t로만 구성된 길이 의 문자열로 생각하자. 알파벳 s는 소세지를, t는 떡을 의미한다.
위 그림은 길이가 인 소떡소떡의 예시이다. 유진이는 소떡소떡을 먹기 전에 이를 균형 잡힌 소떡소떡으로 만들려고 한다. 꼬치에 꽂힌 소세지와 떡의 개수가 같으면 균형 잡힌 소떡소떡이라고 한다. 단, 소세지와 떡이 한 개도 꽂혀 있지 않다면 균형 잡힌 소떡소떡이 아니다.
위 그림은 소세지가 개, 떡이 개 꽂혀 있으므로 균형 잡힌 소떡소떡이 아니다. 유진이는 소떡소떡의 맨 왼쪽에 있는 소세지나 떡을 떼어낼 수 있다. 오른쪽은 손잡이이므로 오른쪽에서 떼어내는 것은 불가능하다. 아래 그림은 맨 왼쪽의 소세지를 떼어낸 모습이다.
이어서 떡 두 개를 더 떼어내면 소세지가 개, 떡이 개 꽂혀 있어 균형 잡힌 소떡소떡이 된다. 유진이가 먹으려고 하는 소떡소떡이 주어질 때, 이 과정을 거쳐 만들 수 있는 길이가 최대인 균형 잡힌 소떡소떡은 어떤 모양일까?
입력
첫째 줄에 소떡소떡의 길이 ()이 주어진다. 둘째 줄에는 소떡소떡을 나타내는 길이 의 문자열이 주어진다. 이 문자열은 s와 t로만 구성된다. 위 과정으로 균형 잡힌 소떡소떡을 만들 수 없는 입력은 주어지지 않는다.
출력
이 과정을 거쳐 만들 수 있는 길이가 최대인 균형 잡힌 소떡소떡의 모양을 출력한다.