[백준] 문자열 교환 1522번 (🥈실버1)

사이트

https://www.acmicpc.net/problem/1522

1522번: 문자열 교환

문제

분석

볼모으기 문제랑 비슷했다. 볼모으기 문제는 엄청 쉽게 풀었는데 

이 문제는 슬라이딩 윈도우 알고리즘이라고 한다. 즉 문자열의 끝이 처음과 다시 이어지는 원형 구조 인거다

 

뭔가 쉽고 빨리 풀 수 있을거 같았는데 고정관념이 사로잡혔다. 

볼모으기 문제처럼 알파벳 갯수 최소를 찾으면 될줄 알았으나 생각해야 될게 많고 도저히 안풀렸다. 

실버1인데 골드푸는 기분....

 

그래서 생각한 알고리즘은 바로!!

a만 연속으로 쭉 만들면 된다.  예제를 예시로 들때 a는 8개이다.

그래서 처음부터 8개씩 괄호로 묶었다. 저 빨간 괄호안에 있는 b의 갯수는 3개이므로 뒤에 있는 a랑 바꾸면 된다.

딱히 바꿔야 되는 조건이 뭐 있는게 없으므로 막 바꿔도 된다.

두번째로 갔을때는 b는 4개이다. 즉 이렇게 차례차례 가면서 b의 갯수가 최소인것을 구하면 되는 문제였다.

또한 문자열 끝까지 검사해야 된다! 이어져 있으로!! 

 

이제 코드로 보자. 

 

for (int i = 0; i < all; i++) {
    for (int j = i; j < i + a_size; j++) {
        if (j >= all) {
            temp_cnt++;
            break;
        }
        if (message[j] == 'b') {
            b_cnt++;
        }

    }
    if (temp_cnt != 0) {
        for (int k = 0; k < temp_cnt; k++) {
            if (message[k] == 'b') {
                b_cnt++;
            }
        }
    }

    min = Math.min(min, b_cnt);
    b_cnt = 0;
}

 

이게 핵심 코드이다! 차근차근 보자. 

for (int i = 0; i < all; i++) {
    for (int j = i; j < i + a_size; j++) {
        if (j >= all) {
            temp_cnt++;
            break;
        }
        if (message[j] == 'b') {
            b_cnt++;
        }

    }

 

첫번째 for문에서는 모든 문자 위치 경우의 수를 세워야 되므로 all로 놓았고 

두번째 for문에서는 그 해당 문자 위치 기준으로 a의 갯수만큼 돌리면 된다. 

근데 만약 이런 경우에는 문자열이 벗어나므로 temp_cnt로 횟수를 하나하나씩 축저해간다. 

for (int j = i; j < i + a_size; j++) {
    if (j >= all) {
        temp_cnt++;
        break;
    }

즉 여기서 all이 15이므로 j가 이젠 16이 됐을때 temp_cnt 하나 올라가고 break 되면서 

if (temp_cnt != 0) {
    for (int k = 0; k < temp_cnt; k++) {
        if (message[k] == 'b') {
            b_cnt++;
        }
    }
}

여기서 다시 처음부터 돌아가 temp_cnt 만큼 b의 갯수를 센다

 

또 두번째 타임에서 j가 17이 됐을때 기존 temp_cnt는 초기화를 안해줬으므로 계속 축적해서 정답을 구할 수 있다. 

전체코드

package bra;

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

public class Bra1522 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String original = br.readLine();
        char[] message = new char[original.length()];
        int min = Integer.MAX_VALUE;
        int a_size = 0;
        int all = original.length();

        for (int i = 0; i < original.length(); i++) {
            message[i] = original.charAt(i);
            if (original.charAt(i) == 'a') {
                a_size++;
            }
        }
        int temp_cnt = 0;
        int b_cnt = 0;

        for (int i = 0; i < all; i++) {
            for (int j = i; j < i + a_size; j++) {
                if (j >= all) {
                    temp_cnt++;
                    break;
                }
                if (message[j] == 'b') {
                    b_cnt++;
                }

            }
            if (temp_cnt != 0) {
                for (int k = 0; k < temp_cnt; k++) {
                    if (message[k] == 'b') {
                        b_cnt++;
                    }
                }
            }

            min = Math.min(min, b_cnt);
            b_cnt = 0;
        }
        System.out.println(min);
    }
}

결과

느낀점

하 진짜 저번 볼모으기 문제랑 너무 유사해서 방법을 기존껄로 생각하다가 큰 코 다친 문제였다...

그래도 풀긴 풀었으니깐 ㅎㅎ