백준 1522번 문자열 교환 - 자바(Java)

문제 링크

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

 

 

---

1. 문제

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

abababababababa

예제 출력 1 복사

3

예제 입력 2 복사

ba

예제 출력 2 복사

0

예제 입력 3 복사

aaaabbbbba

예제 출력 3 복사

0

예제 입력 4 복사

abab

예제 출력 4 복사

1

예제 입력 5 복사

aabbaaabaaba

예제 출력 5 복사

2

예제 입력 6 복사

aaaa

예제 출력 6 

0

 

반응형

2. 문제 관찰 과정 및 풀이

2-1. 문제 관찰 과정

처음 문제를 풀때에는 투포인터를 사용하여 풀었다.

a와 b의 갯수를 구해서 갯수가 작은 문자를 검사하면서 위치를 바꾸어 주려하였다.

package baekjoon;

import java.io.*;
import java.util.Collections;

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

        char[] arr = input.toCharArray();

        int start =0;
        int end = arr.length - 1;

        //a와 b중 어느것이 더 적은지 확인
        int acount = 0;
        int bcount = 0;

        for(char c : arr){
            if(c == 'a'){
                acount++;
            }else{
                bcount++;
            }
        }
        boolean flag = false;
        int count = 0;


        //우선 b가 작다고 가정
        while(start <= end) {
            if(arr[start] == 'a' && flag && arr[end] == 'b'){ //b 다음 a라면
                arr[start] = 'b';
                arr[end] = 'a';
                count++;
                start++;
                end--;
            }
            else if(arr[start] == 'b' && !flag){ //b를 만나면 flag true로 하고 start이동
                flag = true;
                start++;
            }
            else if(arr[start] == 'a' && !flag){
                start++;
            }else if (arr[start] == 'b' && flag){
                start++;
            }
            if(arr[end] != 'b'){
                end--;
            }
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }

}

 

하지만 처음 이방식은

aabbbbbbaaaaaaaaaaaabbbbbbbbbbbb와 같은 입력이 주어진다면 제일 뒤의 b를 바꾸기 때문에 고려할 요소들이 너무 많아 어려웠다.

 

그러다 같은 스터디원이랑 코드를 같이 보다가 힌트로 알려주었는데

a와 b의 갯수를 구한뒤 둘중하나를 붙잡고 그 문자의 갯수만큼 슬라이딩 윈도우를 하는 것이다.

처음에 원형 큐를 생각하긴 했었는데...

슬라이딩 윈도우의 좌표를 문자열의 뒤와 앞이 연결되어 있다고 해서 생각하지 못한것 같다.

2-2. 문제 풀이

1. for문으로 각 문자의 인덱스에서 시작해서
2. for문안에서 a의 갯수만큼 윈도우로 검사
3. b의 갯수를 count한뒤에 가장 작은 값을 저장

3. 코드

import java.io.*;
import java.util.Collections;

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

        char[] arr = input.toCharArray();

        int start =0;
        int end = arr.length - 1;

        //a와 b중 어느것이 더 적은지 확인
        int acount = 0;
        int min = Integer.MAX_VALUE;

        for(char c : arr){
            if(c == 'a'){
                acount++;
            }
        }

        //슬라이딩 윈도우의 갯수만큼 있는지 확인
        for(int i = 0; i < arr.length; i++){
            //a의 갯수만큼 돌아가면서
            int count = 0;
            for(int j = 0; j < acount; j++){
                if(arr[ (i +  j) % arr.length] == 'b'){
                    count++;
                }

            }
            min = Math.min(min , count);
        }
        bw.write(String.valueOf(min));
        bw.flush();
        bw.close();
        br.close();
    }

}

 

3-1. 실행 결과

4. 여담

처음 생각했던 방법의 방향성은 맞았다고 생각한다...

그리고 a와 b의 갯수를 카운트한뒤 진행한다면 좀더 시간이 짧을까 생각했다.