25641. 균형 잡힌 소떡소떡

[Bronze III] 균형 잡힌 소떡소떡 - 25641

문제 링크

성능 요약

메모리: 108080 KB, 시간: 112 ms

분류

구현, 문자열

제출 일자

2023년 11월 13일 19:22:39

문제 설명

소떡소떡은 기다란 꼬치에 소세지와 떡을 끼운 음식이다. 편의상 소떡소떡을 알파벳 s와 t로만 구성된 길이 $N$의 문자열로 생각하자. 알파벳 s는 소세지를, t는 떡을 의미한다.

위 그림은 길이가 $7$인 소떡소떡의 예시이다. 유진이는 소떡소떡을 먹기 전에 소떡소떡을 균형 잡힌 소떡소떡으로 만들려고 한다. 꼬치에 꽂힌 소세지와 떡의 개수가 같을 때 이를 균형 잡힌 소떡소떡이라고 한다. 단, 소세지와 떡이 한 개도 꽂혀있지 않다면 균형잡힌 소떡소떡이 아니다. 위 그림은 소세지가 $3$개, 떡이 $4$개 꽂혀 있기 때문에 균형 잡힌 소떡소떡이 아니다.

유진이는 소떡소떡의 맨 왼쪽에 있는 소세지나 떡을 떼어낼 수 있다. 오른쪽은 손잡이 부분이기 때문에 오른쪽에서 떼어내는 것은 불가능하다. 위 그림은 소떡소떡의 맨 왼쪽에 있던 소세지를 떼어낸 그림이다.

위 그림은 떡 두 개를 더 떼어낸 그림이다. 소세지가 $2$개, 떡이 $2$개 꽂혀 있기 때문에 균형 잡힌 소떡소떡이 되었다.

유진이가 먹으려고 하는 소떡소떡이 주어질 때, 이러한 과정을 통해 만들 수 있는 길이가 최대인 균형 잡힌 소떡소떡은 어떤 모양일까?

입력

첫째 줄에 소떡소떡의 길이 $N(2 \le N \le 100)$이 주어진다.

둘째 줄에 소떡소떡을 의미하는 길이 $N$의 문자열이 주어진다. 이 문자열은 알파벳 s와 t로만 구성되어 있다.

위 과정을 통해 균형 잡힌 소떡소떡으로 만들 수 없는 입력은 주어지지 않는다.

출력

이러한 과정을 통해 만들 수 있는 길이가 최대인 균형 잡힌 소떡소떡의 모양을 출력한다.