[백준] 1522 문자열 교환 - 슬라이딩 윈도우(Sliding Window) JAVA

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

코드설명

슬라이딩 윈도우(Sliding Window)를 활용합니다.

 

우선, 슬라이딩 윈도우(Sliding Window)와 투포인터(Two Pointer)는 비슷한 개념같지만 다릅니다.

슬라이딩 윈도우의 경우는 항상 창의 크기가 고정되어있기에, left, right와 같은 투포인터가 필요하지 않습니다. (물론 사용해도 되지만, 없는채로 구현이 가능하므로 사용하지 않습니다.)

반면, 투포인터의 경우 언제든 창의 크기가 변경되고, 그렇기에 left와 right 투포인터를 활용하여 작동합니다.

 

이떄, 이 문제의 경우 슬라이딩 윈도우를 활용해 창을 만들어서 이동시켜야 합니다.

이떄 창의 크기는 어떻게 될까요? 바로 해당 문자열의 'a'의 개수입니다. 이를 통해 해당 창에서 가장 적은 개수의 'b'를 찾을 수 있는 것이지요. 이때 원형 배열의 특성을 이용해야 하는 것은 덤입니다.

원형 배열의 특성을 사용할때 index=0으로부터 시작하도록 처리했으므로 

(i + aCnt -1) % arr.length로 처리해주어야 합니다.  -1을 처리해주는 이유는 i번쨰 위치도 숫자 1로 Counting하기에 그렇습니다. 

코드

슬라이딩 윈도우 방식입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static char[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		arr = st.nextToken().toCharArray();
		System.out.println(slidingWindow());
	}
	
	static int slidingWindow() {
		int aCnt = 0;
		int bCnt = 0;
		int minSwapCnt = 1001;
		for(int i=0; i<arr.length; i++) {
			if(arr[i] == 'a') aCnt += 1;
		}
		
		for(int i=0;i<aCnt; i++) {
			if(arr[i] == 'b') bCnt += 1;
		}
		
		int windowSize = aCnt;
		minSwapCnt = bCnt;
		for(int i=1; i<arr.length; i++) {
			int beforeIdx = i - 1;
			int nextIdx = (i + aCnt - 1) % arr.length;
			
			if(arr[beforeIdx] == 'b') bCnt -= 1;
			if(arr[nextIdx] == 'b') bCnt += 1;
			
			minSwapCnt = Math.min(minSwapCnt , bCnt);
		}
		return minSwapCnt;
	}
	
}

 

 

오답코드1입니다. 처음에 어느 한점이 '기준'이 되어야 한다고 생각했습니다.

저의 경우에는 왼쪽에서부터 left가 이동하며 모든 'b'를 왼쪽으로 몰아주는 것을 생각하여 구현했습니다.

bbaabbbb

하지만 반례가 존재합니다.

위의 경우 답은 0이어야 합니다만, 저의 코드에서는 2가 됩니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static char[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		arr = st.nextToken().toCharArray();
		System.out.println(twoPointer(0, arr.length - 1));
	}
	
	static int twoPointer(int lo, int hi) {
		int left = lo;
		int right = hi;
		int ret = 0;
		for(int i=0; i<arr.length;i++) {
			if(arr[i] == 'b') {
				left = i;
				break;
			}
		}
		
		while(left + 1 <= right) {
			if(arr[left] == 'b') {
				left += 1; continue;
			}
			if(arr[right] == 'a') {
				right -= 1; continue;
			}
			if(arr[left] == 'b' && arr[right] == 'b') {
				
			}
			if(arr[left] == 'a' && arr[right] =='b') {
				ret += 1;
				arr[left] = 'b';
				arr[right] = 'a';
			}
		}
		
		return ret;
	}
	
}