백준 15831번: 준표의 조약돌 [투 포인터][구간합][누적합] -Java

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

15831번: 준표의 조약돌

서브태스크가 있는 문제.

누적합+투 포인터 알고리즘을 사용해야 모든 문제 성공,,

 

728x90

 

<Java 코드 - 부분 성공, 100점>

Small 태스크는 성공했으나 Large는 시간초과

 

대략적인 풀이법은 누적합을 구해놓고

i = 0 ~ N 까지 돌면서 j 도 i ~ N 만큼 돌아준다. 

이중 포문인 셈... 왜 뭐 저렇게 어렵게 구현했지?

O(N^2) 기에 당연 시간초과 날수밖에!

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		
		char arr[] = new char[N]; //조약돌 배열
		int sum[][] = new int[N][2]; //누적합 배열
		
		st = new StringTokenizer(br.readLine());
		String str= st.nextToken();
		
		arr[0] = str.charAt(0);
		sum[0][0] = str.charAt(0) == 'B'? 1:0;
		sum[0][1] = str.charAt(0) == 'W'? 1:0;
		
		for (int i = 1; i < N; i++) {
			char ch = str.charAt(i);
			arr[i] = ch;
			
			//누적합 세팅
			if(ch == 'B') {
				sum[i][0] = sum[i-1][0]+1;
				sum[i][1] = sum[i-1][1];
			} else {
				sum[i][0] = sum[i-1][0];
				sum[i][1] = sum[i-1][1]+1;
			}
		}

		//구간 조사
		int j = 1;
		int res = 0;
		for (int i = 0; i < N; i++) {

			if(j==N)
				j=i;
			
			while(j<N && j>=i) {
				int cntB = sum[j][0] - sum[i][0] + (arr[i] == 'B'? 1:0);
				int cntW = sum[j][1] - sum[i][1] + (arr[i] == 'W'? 1:0);
//				System.out.println(cntB+" , "+cntW+"..."+i+"/"+j);
				if(cntB <= B && cntW >= W) { //조건에 만족하는지?
//					System.out.println("!!");
					res = Math.max(res, j-i+1);
				} 
				j++;
			}	
			
		}
		
		System.out.println(res);
	}
	
}

 

728x90

 

<Java 코드 - 성공 , 250점>

투 포인터를 적용한 알고리즘이다.

Small, Large 모두 성공

 

만일 [4:7] 구간은 만족하고  [4:8] 의 구간이 조건을 만족하지 못한다면

[5:5]부터 [5:6],[5:7]... 다 보는 것이 아닌 [5:8] 부터 본다. 그게 더 쉽다.

 

[4:8] 구간의 조약돌 갯수에서 위치 [4]의 조약돌 갯수만 빼주면  [5:8] 구간의 조약돌 갯수를 구할 수있다.

여기서 만약에 [5:8]이 조건을 만족하면 [5:5]~[5:7]는 볼필요도 없이 조건을 만족한다는 의미이다. 

그렇다면 [5:9]로 바로 넘어가면 된다.

 

그런데 [5:8]이 조건을 불만족한다면.. 범위를 좁혀서 [6:8]을 확인해본다.

왜 [5:7]로 안보고 [6:8]로 보냐면..

[4:7] 구간이 만족하는 것을 앞에서 확인했기때문에 [5:7]도 당연 만족할 것이다.

그치만 [4:7], [5:7] 중에 [4:7]의 구간이 더 길기때문에 굳이 [5:7]은 구해봤자 Math.max에서 밀릴게 뻔하다.

그렇기에 굳이 구하지 않는 것.

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		
		char arr[] = new char[N]; //조약돌 배열
		int sum[][] = new int[N][2]; //누적합 배열
		
		st = new StringTokenizer(br.readLine());
		String str= st.nextToken();
		
		arr[0] = str.charAt(0);
		sum[0][0] = str.charAt(0) == 'B'? 1:0;
		sum[0][1] = str.charAt(0) == 'W'? 1:0;
		
		for (int i = 1; i < N; i++) {
			char ch = str.charAt(i);
			arr[i] = ch;
			
			//누적합 세팅
			if(ch == 'B') {
				sum[i][0] = sum[i-1][0]+1;
				sum[i][1] = sum[i-1][1];
			} else {
				sum[i][0] = sum[i-1][0];
				sum[i][1] = sum[i-1][1]+1;
			}
		}

		//투포인터
		int res= 0;
		int i = 0;
		int j = 0;
		
		while (j < N && i < N) {
			
			int cntB = sum[j][0] - sum[i][0] + (arr[i] == 'B'? 1:0);
			int cntW = sum[j][1] - sum[i][1] + (arr[i] == 'W'? 1:0);
//			System.out.println(cntB+" , "+cntW+"..."+i+"/"+j);

			if(cntB <= B) {
				//조건 만족하면 j++; 구간 길이 늘리기
				if(cntW >=W)
					res = Math.max(res, j-i+1);
				j++;
			} else {
				//불만족하면 i++; 구간 쫍혀서 다시 보기
				i++;
			}
		}
		
		System.out.println(res);
	}
	
}