1522 문자열 교환 [JAVA]

문제 분석

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

a와 b로 이루어진 문자열이 주어진다.

주어진 문자열에서 원소들을 swap하여 a를 모두 이어붙이고자 한다.

이때, 주어진 문자열의 맨 앞과 맨끝은 붙어있는 형태, 즉 원형이라고 할 때 a를 모두 이어붙이기 위한 최소 swap 수는 ?

 

문제를 어렵게 생각하면 미궁에 빠질 수 있지만,, 조금 더 간단하게 생각해보자

 

우선, 맨 앞과 맨 뒤는 이어져 있다. 그렇기에 배열에서 굳이 떨어트려놓을 필요가 없다.

따라서 아래처럼 문자열을 바꿔서 생각을 해보자

abababababababa => aababababababab

 

어떤게 가장 효율적으로 a,b를 스왑하게 되는걸까 ?

 

이미 맨뒤의 a들을 맨 앞으로 옮겨놨으니 사실 원형이라는 조건은 이제 잊어도된다.

그러면, 맨앞에서 부터 a를 이어나가야 한다.

그렇기에 우리는 맨 앞에서 부터 a를 이어붙이다 만난 b를 맨 뒤로 보내야 한다.

 

따라서, 이 swap 과정에서 맨 앞에서 부터 b를 맨 뒤에서부터 a를 찾고 서로를 swap하면 된다.

 

이 과정을 거치게 되면 결국 주어진 상태에서 최소의 swap으로 a를 연결시킬 수 있게 된다.

 

또, abbbaaab처럼 맨 처음의 a부터 이어붙이는게 가장 효율적이지 않은 경우가 있다.

즉, 문자열의 a로 시작하는 부분들에 대해 위의 swap 과정을 모두 거치고 이 중 가장 적은 횟수를 찾아 답으로 리턴하면 된다.

 

예를 들면

 

aababababababab

 

abababababab aab

 

ababababab aabab

 

abababab aababab

 

ababab aabababab

 

abab aababababab

 

ab aabababababab

이런식으로 처음 만들었던 문자열에서 a가 시작되는 부분들을 나누어 탐색을 하면 된다.

 

주의할 점은, b로만 구성된 문자열의 경우에도 정답은 0이다. (이건 문제 조건에 좀 써줬으면 좋았을거같다)

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        char[] ca = sc.nextLine().toCharArray();
        int backCnt = 0;
        for(int i=ca.length-1; i>=0; i--){
            if(ca[i] == 'b')
                break;
            backCnt++;
        }

        char[] originArr = new char[ca.length];
        for (int i = 0; i < backCnt; i++) {
            originArr[i] = 'a';
        }

        for (int i = backCnt; i < ca.length; i++) {
            originArr[i] = ca[i-backCnt];
        }

        Set<Integer> startingPoints =new HashSet<>();
        if(originArr[0] == 'a')
            startingPoints.add(0);
        for (int i = 1; i < originArr.length; i++) {
            if(originArr[i] == 'a' && originArr[i-1]=='b')
                startingPoints.add(i);
        }

        int minChangeCount = Integer.MAX_VALUE;

        for (Integer startingPoint : startingPoints) {
            char[] targetArr = new char[originArr.length];
            for (int i = 0; i < originArr.length; i++) {
                int customIdx = startingPoint+i >= originArr.length ? startingPoint+i-originArr.length : startingPoint+i;
                targetArr[i] = originArr[customIdx];
            }

            int nowChangeCount = 0;
            for (int i = 0; i < targetArr.length; i++) {
                if(targetArr[i] == 'b'){
                    boolean isSwapped = false;
                    for (int j = targetArr.length-1; j>i;j--) {
                        if(targetArr[j] == 'a'){
                            isSwapped = true;
                            targetArr[j] = 'b';
                            targetArr[i] = 'a';
                            break;
                        }
                    }
                    if(isSwapped)
                        nowChangeCount++;
                    else
                        break;
                }
            }
            minChangeCount = Math.min(minChangeCount, nowChangeCount);
        }

        System.out.println(minChangeCount == Integer.MAX_VALUE ? 0 : minChangeCount);

    }






}