백준 [자바 java] 1522 : 문자열 교환

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

 

이 문제는 최소한의 횟수로 노드를 교환하여 같은 문자열끼리 나열되도록 하는 문제이다

 

처음엔 bfs로 풀어야하나(그놈의 bfs...)했는데 아무리 생각해도 너무 오래걸린다고 생각했다.

알고보니까 슬라이딩윈도우라는 알고리즘으로 풀어야한다고 한다.

슬라이딩 윈도우는 네트워크 할 때 봤다!

탐색해야하는 배열의 범위가 주어진다면 처음부터 끝까지 한칸씩 이동하면서 가능한 배열의 가짓수를 모두 탐색하는 것이다.

 

여기서는 모든 a가 일렬로 나열되어야하므로, a의 갯수만큼 탐색을 해주었다.

 

aabbbaba 이런 배열이 있으면 여기서는 a가 4개이다.

(aabb)baba 이 경우는, b가 윈도우 내 2개이므로, 2번 교환을 해야한다.

a(abbb)aba 이 경우는 b가 윈도우 내 3개이므로 3번 교환을 해야한다.

이런식으로 모든 경우를 탐색하고, 윈도우 내 b의 갯수가 최소인 곳의 b의 갯수를 구하면 된다.

 

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    char[] arr = br.readLine().toCharArray();

    int cnt = 0;

    for(int i =0 ;i<arr.length;i++){
      if(arr[i] == 'a') cnt++;
    }

    int ans = cnt;

    int n = arr.length;

    for(int i = 0;i<n;i++){
      int now = 0;
      for(int j = i;j<i+cnt;j++){
        if(arr[j%n] == 'b') now++;
      }
      ans = Math.min(ans,now);
    }

    System.out.println(ans);
  }
}

 

전체코드이다.

여기서는 0번노드와 n-1번 노드가 연결되어있으므로, n, n+1을 탐색할 때에는 n의 나머지를 탐색하게하였다.(0,1을 탐색하게 됨)