[백준 - 15831] 준표의 조약돌 .java

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

 

• 문자열에서 연속된 부분 문자열
• B의 최대 개수가 bMax 이하
• W의 최소 개수가 wMin 이상
• 가장 긴 부분 문자열의 길이

=> 가장 긴 부분을 찾는 것 => 최대 개수을 넘어가면 더이상 추가 불가능 -> i증가

=> 최대 개수안에서 w의 최소 개수를 만족시키는 구간의 길이 구하기 

=> next : 현재의 다음 인덱스를 가리킴 (오른쪽 포인터)

=> 두 포인터 사이의 구간 : next는 포함안됨 -> next-i

 

 

1. 두개의 조건중 최대 개수를 넘지 않을 동안 계속 추가
2. 추가한 구간이 w의 최소 조건을 만족시키는지  검사
3. 만족하면 최댓값으로 갱신
4. 현재 i에서 시작하는 구간은 다 해봄 -> i증가 => 해당 개수 줄이기

 

import java.util.Scanner;


public class Solution {

    public static void main(String[] args)  {
    	
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int bMax = sc.nextInt();
    	int wMin = sc.nextInt();
    	
    	char[] works = sc.next().toCharArray();
    	
    	int curB = 0;
    	int curW =0;
    	int next = 0;//오른쪽 포인터 역할
    	int answer = 0;//구간의 최대 길이
    	
    	for(int i  =0; i<n;i++) {
    		while(next < n) {
                //더이상 b는 추가할 수 없음
    			if(curB == bMax && works[next]=='B') break;
    			//현재 문자에 따라 개수 증가
    			if(works[next++]=='W') curW++;
    			else curB++;
    		}
            //조건을 만족하면 구간 길이 최댓값 갱신
    		if(curW >=wMin)
    			answer = Math.max(answer,next-i);
                
             //i를 구간에서 빼기
    		 if(works[i]=='B') curB--;
    		 else curW--;
    	}
    	System.out.print(answer);
    	
     }
    
}