방과후
ALGORITHM NOTE약 1분

BOJ 20442 - ㅋㅋ루ㅋㅋ

ㅋㅋ루ㅋㅋ

#algorithm#boj#gold#two-pointers#prefix-sum
아카이브로 돌아가기

문제 링크

문제

ㅋㅋ루ㅋㅋ 문자열은 다음과 같이 정의한다.

  1. R로만 이루어진 문자열은 ㅋㅋ루ㅋㅋ 문자열이다. 단, 빈 문자열은 ㅋㅋ루ㅋㅋ 문자열이 아니다.
  2. ㅋㅋ루ㅋㅋ 문자열 양 끝에 K를 하나씩 붙인 문자열은 ㅋㅋ루ㅋㅋ 문자열이다.

입력

첫째 줄에 K와 R로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 3,000,000이다.

출력

주어진 문자열의 부분 수열 중 가장 긴 ㅋㅋ루ㅋㅋ 문자열의 길이를 출력한다. 부분 수열 중 ㅋㅋ루ㅋㅋ인 문자열이 없는 경우, 0을 출력한다.

풀이

결국 선택되는 형태는 K ... K + R...R + K ... K다. 가운데에 고른 R 묶음의 양옆에 몇 개의 K를 붙일 수 있는지가 중요하다.

코드에서는 먼저 전체 R의 개수를 세고, 각 R 기준으로 왼쪽에 있는 K 개수와 오른쪽에 있는 K 개수를 각각 배열처럼 저장한다. 그러면 left번째 R부터 right번째 R까지를 가운데 묶음으로 택했을 때, 붙일 수 있는 K 수는 양쪽 중 더 작은 값으로 결정된다.

이후 R들 위에서 투 포인터를 움직인다. 현재 양쪽 K 가능 개수 중 작은 쪽이 병목이므로, 그쪽 포인터를 줄이는 방식으로 최적해를 찾는다. 매번 후보 길이는 가운데 R 개수 + 2 * min(왼쪽 K, 오른쪽 K)가 된다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int ans = solve(input);
        System.out.println(ans);
    }
 
    static int solve(String input) {
        int rCnt = getRCnt(input);
        List<Integer> leftK = checkLeftK(input);
        List<Integer> rightK = checkRightK(input);
 
        int ans = 0;
        int cnt = rCnt;
        int left = 0;
        int right = rCnt - 1;
 
        while (left <= right) {
            if (leftK.get(left) < rightK.get(right)) {
                ans = Math.max(ans, leftK.get(left) * 2 + cnt);
                left++;
            } else {
                ans = Math.max(ans, rightK.get(right) * 2 + cnt);
                right--;
            }
            cnt--;
        }
 
        return Math.max(ans, rCnt);
    }
 
    // R 개수 구하기
    static int getRCnt(String input) {
        int rCnt = 0;
 
        for (int i = 0; i < input.length(); i++)
            if (input.charAt(i) == 'R')
                rCnt++;
 
        return rCnt;
    }
 
    // R 기준 왼쪽에 있는 누적 K개수 구하기
    static List<Integer> checkLeftK(String input) {
        List<Integer> leftK = new ArrayList<>();
 
        int kCnt = 0;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == 'R')
                leftK.add(kCnt);
            else
                kCnt++;
        }
 
        return leftK;
    }
 
    // R 기준 오른쪽에 있는 누적 K개수 구하기
    static List<Integer> checkRightK(String input) {
        List<Integer> rightK = new ArrayList<>();
 
        int kCnt = 0;
        for (int i = input.length() - 1; i >= 0; i--) {
            if (input.charAt(i) == 'R')
                rightK.add(kCnt);
            else
                kCnt++;
        }
 
        Collections.reverse(rightK);
        return rightK;
    }
}

복잡도

  • 시간 복잡도: O(N)O(N)
  • 공간 복잡도: O(N)O(N)

마무리

문자열 정의는 귀엽지만, 실제로는 가운데 R 구간과 양옆 K 개수의 균형을 보는 문제다. 양쪽 중 작은 쪽이 항상 병목이라는 점 때문에 투 포인터가 잘 맞는다.