[Baekjoon/C++] 25641번 - 균형 잡힌 소떡소떡

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

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

 

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

 

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

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

 

입력

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

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

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    string st;
    
    cin >> N >> st;

    int s = 0; // 소세지의 수
    int t = 0; // 떡의 수

    // 소세지와 떡의 수 구하기
    for (int i = 0; i < N; i++) {
        if (st[i] == 's') s++;
        else t++;
    }

    // 균형 잡힌 소떡소떡 만들기
    int idx = 0;
    for (int i = 0; i < N; i++) {
        if (s == t) {
            idx = i;
            break;
        }

        if (st[i] == 's') s--;
        else t--;
    }

    // 출력
    for (int i = idx; i < N; i++) cout << st[i];
    cout << '\n';

    return 0;
}

 소세지와 떡의 개수를 구하고, 왼쪽부터 소세지/떡을 하나씩 빼면서 수를 비교한다. 그러다 두 재료의 수가 같아진다면 균형 잡힌 소떡소떡을 구한 것이다.