[JAVA] 20442 ㅋㅋ루ㅋㅋ

난이도

골드2 

 

알고리즘: 투 포인터

문제 풀이를 위해 파악해야 할 중요한 점은 두 가지이다.

1. 입력 문자열의 길이는 최대 3,000,000이다.
2. ㅋㅋ루ㅋㅋ 문자열은 좌우대칭이다.

우선 입력이 크기 때문에 최대한 O(N)으로 연산을 해야한다. 즉 문자열의 각 원소에 대해 한번만 탐색하고 지나가는 풀이를 고안해야 한다는 것이다. 두번째로 ㅋㅋ루ㅋㅋ 문자열은 R을 중심으로 같은 개수의 K가 양 쪽에 붙은 좌우 대칭이다. 이 두 가지 특징을 통해 투 포인터를 떠올릴 수 있어야 한다.

 

투 포인터까지 떠올렸으면, 이제 각 포인터를 어떻게 움직여야 할 지 생각해야 한다. ㅋㅋ루ㅋㅋ 문자열은 K 사이에 R이 있는 문자열이다. (물론 K는 없을 수 있음) 따라서 투 포인터 바깥의 K와 안 쪽의 R로 ㅋㅋ루ㅋㅋ 문자열을 생성한다.

 

 

위와 같이 포인터를 움직일 수록 문자열의 K 개수는 많아지고, R 개수는 적어진다. 따라서 K 개수를 많아지게 하는 포인터를 움직여야 한다. 

while(left <= right):
    if(left쪽 K 개수 < right쪽 K 개수):
    	left++
    else:
    	right++

또한 포인터를 움직이고 나서, 해당 포인터가 R을 가리킨다면 현재 문자열에서 R의 개수가 하나 줄어들었기 때문에 문자열이 바뀌었다. 따라서 바뀐 문자열의 길이가 이전보다 긴 지 비교한다.

while(left <= right):
    if(left쪽 K 개수 < right쪽 K 개수):
    	left++
        if(현재 문자열의 길이 > 최대 문자열의 길이):
            최대 문자열의 길이 = 현재 문자열의 길이
    else:
    	right++
        if(현재 문자열의 길이 > 최대 문자열의 길이):
            최대 문자열의 길이 = 현재 문자열의 길이

현재 문자열의 길이를 재려면, 현재 문자열을 구성하는 K의 개수와 R의 개수를 알아야 한다. K의 개수는 포인터를 움직이며 하나씩 더해주면 되지만 R의 개수는 따로 구해야 하기 때문에 미리 전체 R의 개수를 구해준다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringBuilder sb;

    static String string;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        string = br.readLine();
        
        /* 전체 R의 개수 계산 */
        int rCnt = 0;
        for(int i = 0; i < string.length(); i++) {
            if(string.charAt(i) == 'R') rCnt++;
        }

        /* 알고리즘 */
        int maxLength = rCnt;
        int left = 0, right = string.length() - 1;
        int leftKCnt = 0, rightKCnt = 0;

        while(left <= right) {
            if(leftKCnt < rightKCnt) {
                if(string.charAt(left++) == 'R'){
                    maxLength = Math.max(maxLength, Math.min(leftKCnt, rightKCnt) * 2 + rCnt--);
                }else leftKCnt++;
            } else {
                if(string.charAt(right--) == 'R'){
                    maxLength = Math.max(maxLength, Math.min(leftKCnt, rightKCnt) * 2 + rCnt--);
                }else rightKCnt++;
            }
        }

        sb.append(maxLength).append('\n');
        bw.write(sb.toString());
        bw.flush();
    }
}

따라서 최종 코드는 다음과 같다.