[백준/JAVA] 1522번: 문자열 교환

🔺 문제

1522번: 문자열 교환

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str = br.readLine();
        int min = Integer.MAX_VALUE;
        
        int aCnt = 0;
        for(int i = 0 ; i < str.length() ; i++) {
            if(str.charAt(i) == 'a')
               aCnt++;
        }
        
        for(int i = 0 ; i < str.length() ; i++) { // [브루트포스] 0 ~ 마지막 인덱스까지
            int bCnt = 0;
            
            for(int j = i ; j < i + aCnt ; j++) { // 🔔 [슬라이딩 윈도우] 해당 인덱스 ~ 그 위치에서 a길이까지
                if(str.charAt(j % str.length()) == 'b')
                    bCnt++;
            }
            
            min = Math.min(min, bCnt);
        }
        
        System.out.println(min);
    }
}

✅ 해결 아이디어
✔ 슬라이딩 윈도우 + 브루트포스
1. 주어진 문자열에서 a의 길이를 센다.
2. "교환 횟수의 최솟값" = b가 있다면, b 갯수를 카운팅하고 이 중 최솟값

 

0부터 끝 인덱스까지 시작해서,

그 위치에서 a의 길이까지 살펴보며 b 갯수 카운팅

• ababab -> b 1개 교환

• ababab -> b 2개 교환

• ababab -> b 1개 교환

.

.

.

=> 이 중 교환하는 최솟값이 최소 교환 횟수

 

 

💥 유의사항

• 문자열 범위를 넘어가면, 다시 0번째부터 살펴볼 수 있게하기 (∵ 문자열이 원형으로 이뤄졌으므로)

 

 

---

💬 느낀 점

와 어떻게 이런 생각을 하지,,? 

슬라이딩 윈도우 복습 좀 해야겄다,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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