[백준] 1522. 문자열 교환 (투포인터/Java)

[백준] 1522. 문자열 교환

 

📌 풀이 과정

처음에 문제에서 말하는 "교환"이 도대체 뭔지 이해되지 않았다. 백준 질문게시판을 찾아보니 아래 글을 발견했고,

교환의 정의는 a와 b의 위치를!! 두 문자의 위치를 바꾸는 것이었다.

ㄱㅅ합니다 덕분에 이해했어요

핵심 아이디어

1. a의 개수만큼 연속된 구간을 만들어야 함
2. 그 구간 안에 있는 b들을 밖의 a들과 교환
3. 따라서 구간 내 b의 개수 = 필요한 교환 횟수
4. 모든 시작점에서 윈도우를 슬라이딩하며 최소 b 개수 찾기

그리고 원형 문자열이라는 조건이 주어졌기 때문에

(start + i) % size로 배열 끝에서 처음으로 순환하는 원형 처리를 해주어야 한다.

 

✨ 제출 코드

메모리: 14232 KB

시간: 104 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int window = 0;
        int size = str.length;

        for(int i = 0; i < size; i++){
            if(str[i] == 'a') window++;
        }

        if(window == 0 || window == size) {
            System.out.println(0);
            return;
        }

        int minB = Integer.MAX_VALUE;
        for(int start = 0; start < size; start++){
            int countB = 0;

            for(int i = 0; i < window; i++){
                int idx = (start + i) % size;
                if(str[idx] == 'b') countB++;
            }

            if(countB == 0){
                minB = 0;
                break;
            }

            minB = Math.min(minB, countB);
        }

        System.out.println(minB);
    }
}