(백준) ㅋㅋ루ㅋㅋ _ 20442 [java]

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

 

🐢 설명

R로만 이뤄지면 "ㅋㅋ루ㅋㅋ" 이다.

"ㅋㅋ루ㅋㅋ" 양옆에 K가 붙으면 "ㅋㅋ루ㅋㅋ"이다.

 

주어진 문자열의 부분수열 중 ㅋㅋ루ㅋㅋ인 문자열의 최대 길이를 구한다.

 

부분수열이 가장 핵심적인 내용이다.

 

부분 수열이므로 원하는 부분은 넣고, 아닌 부분은 빼면 되는 그리디하게 문제를 접근하면 된다. 왼쪽 R이 있고, 중간에 뭐가있든 오른쪽 R이 있다면 해당 문자열은 "ㅋㅋ루ㅋㅋ"가 될 수 있다.

 

예를들어 R K K R K K R K K K K R K K R K 일 경우 K를 다 빼버리고 R의 개수만 구해서 "ㅋㅋ루ㅋㅋ"인 문자열로 취할 수 있다는 것이다.

 

하지만 여기서 양옆에 K가 동일한 개수만큼 붙으면 그것 또한 "ㅋㅋ루ㅋㅋ"라고 했으므로 해당 부분을 처리해줘야 한다.

 

이부분은 패딩 K를 최대로 가지게 해야하는데, 왼쪽에서 출발해서 R을 만났을 때 R의 왼쪽에 있던 K 개수와 오른쪽에서 출발해서 R을 만났을 때 R의 오른쪽에 있는 K의 개수의 최소값이 동일한 개수로 패딩할 수 있는 크기이다. 이때 해당 개수 * 2만큼 크기가 늘어나게 된다.

 

왼쪽의 K개수 3개-> KKK RKRRKRKRKRKR KK <오른쪽의 K개수 2개

위와 같은 경우 패딩 K의 최대값은 2가 되고 내부 R의 개수는 7개이므로 7 + 2 * 2 = 11이 된다.

 

KKK RKRRKRKRKR KRKK

최대의 길이는 위와 같이 양옆 패딩을 KKK 로 잡고 내부 R의 개수를 6개로 잡아서 6 + 3 * 2인 12가 최대이다.

 

이를 위해서 각 R에 대해서

• 자신의 왼쪽에 있는 K의 개수를 담는 리스트 lK
• 자신의 오른쪽에 있는 K의 개수를 담는 리스트 rK

이 후 두개의 리스트에 대해서 투포인터로 왼쪽이 가리키는 (lK[left]) K개수가 오른쪽이 가리키는 (rK[right]) K개수보다 적다면 left를 증가시키고, 오른쪽이 가리키는 K개수가 작거나 같다면 right를 증가시켜서 패딩이 될 수 있는 최대 K크기를 찾아주면된다. 이때 지속적으로 "ㅋㅋ루ㅋㅋ"의 최대 길이를 갱신시켜준다.

 

🐢코드

package Gold이상문제_정리;

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

/*
부분 수열이므로 R - (중간 상관 없음) - R 의 구간을 일단 구하고, 양옆에 붙일 수 있는 K개수를 구하면 된다.
 */
public class ㅋㅋ루ㅋㅋ_20442 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        int answer = twoPointer(str);
        System.out.print(answer);
    }

    private static int twoPointer(String s) {
        ArrayList<Integer> lK = new ArrayList<>();
        ArrayList<Integer> rK = new ArrayList<>();

        int kCnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'K') kCnt++;
            else if (s.charAt(i) == 'R') lK.add(kCnt);
        }
        kCnt = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == 'K') kCnt++;
            else if (s.charAt(i) == 'R') rK.add(kCnt);
        }
        rK.sort(Comparator.reverseOrder());

        int left = 0;
        int right = rK.size() - 1;
        int max = 0;

        while (left <= right) {
            // 부분 수열이므로 R의 양끝 구간을 일단 구하고, 바깥 K의 최소값 * 2를 더해준다.
            max = Math.max(max, (right - left + 1) + (2 * Math.min(lK.get(left), rK.get(right))));

            if (lK.get(left) < rK.get(right)) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}

🐢 마무리