만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

균형 잡힌 소떡소떡

면접 대비

시간 제한1초메모리 제한512 MB

요약
왼쪽 끝에서만 문자를 지워서 s와 t의 개수가 같은 가장 긴 문자열을 만드는 문제입니다.
난이도

쉬움10점 중 3점

유형
문자열, 누적 합
정답자
아직 제출이 없습니다

문제

소떡소떡은 기다란 꼬치에 소세지와 떡을 끼운 음식이다. 편의상 소떡소떡을 알파벳 s와 t로만 구성된 길이 NN의 문자열로 생각하자. 알파벳 s는 소세지를, t는 떡을 의미한다. 위 그림은 길이가 77인 소떡소떡의 예시이다. 유진이는 소떡소떡을 먹기 전에 이를 균형 잡힌 소떡소떡으로 만들려고 한다. 꼬치에 꽂힌 소세지와 떡의 개수가 같으면 균형 잡힌 소떡소떡이라고 한다. 단, 소세지와 떡이 한 개도 꽂혀 있지 않다면 균형 잡힌 소떡소떡이 아니다. 위 그림은 소세지가 33개, 떡이 44개 꽂혀 있으므로 균형 잡힌 소떡소떡이 아니다. 유진이는 소떡소떡의 맨 왼쪽에 있는 소세지나 떡을 떼어낼 수 있다. 오른쪽은 손잡이이므로 오른쪽에서 떼어내는 것은 불가능하다. 아래 그림은 맨 왼쪽의 소세지를 떼어낸 모습이다. 이어서 떡 두 개를 더 떼어내면 소세지가 22개, 떡이 22개 꽂혀 있어 균형 잡힌 소떡소떡이 된다. 유진이가 먹으려고 하는 소떡소떡이 주어질 때, 이 과정을 거쳐 만들 수 있는 길이가 최대인 균형 잡힌 소떡소떡은 어떤 모양일까?

입력

첫째 줄에 소떡소떡의 길이 NN(2≤N≤1002 \le N \le 100)이 주어진다. 둘째 줄에는 소떡소떡을 나타내는 길이 NN의 문자열이 주어진다. 이 문자열은 s와 t로만 구성된다. 위 과정으로 균형 잡힌 소떡소떡을 만들 수 없는 입력은 주어지지 않는다.

출력

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

예제3

  1. 예제 1

    입력
    7
    sttstts
    
    예상 출력
    stts
    
  2. 예제 2

    입력
    4
    ttts
    
    예상 출력
    ts
    
  3. 예제 3

    입력
    4
    stst
    
    예상 출력
    stst