백준 1522번 문자열 교환(자바) - 슬라이딩 윈도우#

문자열 교환 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

784

381

332

54.248%

문제

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

출력

첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

예제 입력 1 복사

abababababababa

예제 출력 1 복사

3

예제 입력 2 복사

ba

예제 출력 2 복사

0

---

아이디어를 떠올리기 힘들었던 문제.

그냥 주어진 문자열에서 a의 개수를 센 후 인덱스를 0번부터 마지막 인덱스까지 돌면서 그 지점부터 a의 개수만큼의 길이의 문자열을 보고 b의 개수를 세어준 후 최소값을 출력해주면 된다.

 

만약 문자열이 ababab라면 a의 개수가 3개이고 따라서 aaabbb 같은 a가 연속적인 형태로 바꿔줘야 한다.

따라서 0번 인덱스부터 aba에 b가 1개 있으므로 1개 교환

bab에 b가 2개 있으므로 2개 교환

aba에 b가 1개 있으므로 1개 교환

bab에 b가 2개 있으므로 2개 교환

...

이런 식으로 모든 경우를 고려해준 뒤 이 중 가장 작은 값인 1을 출력하면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int aCnt = 0;
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == 'a') aCnt++;
        }
        for (int i = 0; i < str.length(); i++) {
            int bCnt = 0;
            for (int j = i; j < i + aCnt; j++) {
                if (str.charAt((j + str.length()) % str.length()) == 'b')
                    bCnt++;
            }
            answer = Math.min(answer, bCnt);
        }
        System.out.println(answer);
    }
}

 

참고

[백준] 1522. 문자열 교환 (자바 JAVA) (tistory.com)

[백준] 1522. 문자열 교환 (자바 JAVA)