[백준] 20442 ㅋㅋ루ㅋㅋ

1. 문제

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

20442번: ㅋㅋ루ㅋㅋ

2. 접근방법

가장 긴 ㅋㅋ루ㅋㅋ 찾기

 

ㅋㅋ루ㅋㅋ의 형태를 잘 보면

중간에 RRRR이 있고 양 옆에 같은 갯수의 KKKK 가 있는 형태다.

단 R사이에는 K가 들어가면 안된다.

 

그렇다면 R갯수를 미리 세어 놓고

양 옆의 R만나기 전 K갯수를 세어서 둘 중 작은 수 *2 한 값을 구하면 된다

그 다음은 양 옆의 K 중 더 적은 K 쪽의 R을 넘기고 똑같이 값을 구하면 된다.

R이 더 이상 남지 않았다면 종료하면 된다.

 

나는 편한게 풀이하기 위해 R이 양 옆에서 먼저 시작하는 경우를 제외시키고자

양 옆에 K를 하나씩 붙여주었고 미리 K와 R의 갯수를 세어서 배열에 저장 시킨 뒤 투포인터를 이용했다.

 

cf)

추가로 양 옆의 K의 갯수가 같으면

어느 한쪽에서 움직이던지 만들어지는 ㅋㅋ루ㅋㅋ의 K수가 바뀌지 않으니

양쪽에서 다 움직여주면 된다.

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class G3_20442ㅋㅋ루ㅋㅋ {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String zzfnzz = 'K' + br.readLine() + 'K';
		int lk = -1;
		int rk = -1;
		int rsum = 0;
		char target = 'K';
		int cnt = 0;
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for (int i = 0; i < zzfnzz.length(); i++) {
			if (zzfnzz.charAt(i) == target)
				cnt++;
			if (zzfnzz.charAt(i) != target) {
				arr.add(cnt);
				if (target == 'R')rsum += cnt;
				target = target == 'K' ? 'R' : 'K';
				cnt = 1;
			}
		}
		arr.add(cnt);
		int left = 0;
		int right = arr.size() - 1;
		lk += arr.get(left);
		rk += arr.get(right);
		int max = 0;
		while (rsum > 0) {
			int sum = Math.min(lk, rk)*2+rsum;
			max = Math.max(sum, max);
			int olk = lk;
			if(olk<=rk) {
				rsum -= arr.get(++left);
				lk += arr.get(++left);
			}
			if(olk>=rk) {
				rsum -= arr.get(--right);
				rk += arr.get(--right);
			}
		}
		System.out.println(max);
	}
	
	
}

4. 마치며

갯수를 미리 세어 놓는게 코드짜기는 편하긴 한데

최악엔 300만 크기의 어레이를 만들어야 해서 공간복잡도는 별로인 것 같다.