[자바]백준 25641번 균형 잡힌 소떡소떡 [문자열][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

 

문제 (안 읽고 문제 설명으로 바로 내려가도 된다.)

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

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

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

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

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

 

입력

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

둘째 줄에 소떡소떡을 의미하는 길이 N의 문자열이 주어진다.

이 문자열은 알파벳 s와 t로만 구성되어 있다.

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

출력

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

 

예제

알고리즘 분류

• 구현
• 문자열

문제 설명

문제 설명이 상당히 길다.

하지만 결국 엄청 단순한 문제다.

s와 t로 이루어진 단어가 주어지는데, s와 t의 개수가 같게 하고 단어의 길이가 최대가 되는 단어를 출력하는 문제다.

단, s와 t는 앞에부터 제거가 가능하다. 

해설

그냥 단순하게 생각해 보자, 앞에 부터 s나 t를 제거해서 s와 t의 개수가 같아지는 시점부터 단어를 출력하면 된다.

밑에 풀이 방식으로 풀면 된다. 제거한다고 해서 문자열에서 s나 t를 없애주는 코드를 넣어줄 필요 없이 제외했다고 가정하고 진행하면 된다. 

1. s와 t의 개수를 파악하기
2. s와 t의 개수가 동일하다면, 현재 인덱스 ~ 단어 끝까지 출력
3. s와 t의 개수가 다르다면, 현재 인덱스의 해당하는 알파벳의 카운트를 빼주고 다음 인덱스로 넘어가기

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        String s = br.readLine();
        
        int sCount = 0;
        int tCount = 0;
        
        for (int i = 0; i < s.length(); i++) {
           if (s.charAt(i) == 's') {
                sCount++;
            } else if (s.charAt(i) == 't') {
                tCount++;
            }
        }
        
        for (int i = 0; i < s.length(); i++) {            
            if (sCount == tCount) {
                bw.write(s.substring(i) + "\n");
                break;
            } else if (s.charAt(i) == 's') {
                sCount--;
            } else if (s.charAt(i) == 't') {
                tCount--;
            }
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}