백준 20442 ㅋㅋ루ㅋㅋ Kotlin (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/20442

20442번: ㅋㅋ루ㅋㅋ

문제

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

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

입력

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

출력

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

힌트

어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다.

알고리즘 분류

• 문자열
• 두 포인터

풀이

투 포인터 문제다.

KKKRKKRRKK 입력을 예로 들어보자.

문제에서 부분 수열은 주어진 입력의 요소들을 순서만 지키면 마음대로 조합할 수 있다.

위의 예시에서

KKKRKKRRKK

KKKRKKRRKK

KKKRKKRRKK

KKKRKKRRKK

등의 경우가 가능한데, 여기서 관건은 R의 왼쪽과 오른쪽에 K의 개수이다.

KKRK 같은 경우 R을 기준으로 왼쪽에 K가 2개, 오른쪽에 K가 1개 이므로 K는 한 쌍만 쓸 수 있다.

KKRRK도 마찬가지로 두 개의 R중 무엇을 기준으로 삼든 K는 한 쌍만 쓸 수 있다. 

KKRKR의 경우 왼쪽 R 기준으로는 K를 한 쌍, 오른쪽 R 기준으로는 K를 쓸 수 없다.

KKRKRKK의 경우 왼쪽 R, 오른쪽 R 모두 K를 두 쌍 쓸 수 있다.

위 3가지 경우의 정답은 뭘까

KKRK = 3

KKRRK = 4

KKRKR = 4

KKRKRKK = 6

즉 leftR ~ rifgtR 사이에 있는 R의 개수와(껴있는 K는 안 쓰면 그만) 사용 가능한 K 쌍의 개수 *2 만큼이 정답이 된다.

 

따라서 풀이는 다음과 같다.

leftR[i] = R이 있는 i 기준으로 왼쪽에 있는 K의 개수

rightR[i] = R이 있는 i 기준으로 오른쪽에 있는 K의 개수

우리는 위 배열에서 K의 위치는 필요 없기 때문에 각 R마다 왼쪽, 오른쪽 K 개수를 저장하기 때문에 input의 길이만큼 배열을 선언하는 게 아니라 ArrayList로 동적으로 만들어 주자.

 

그리고 투 포인터를 이용한다.

s = 0

e = leftR.size -1 or rightR.size -1

answer = min(answer, (e-s+1) + min(leftR[s], rightR[e]) * 2)

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()) {

    //input
    val input = br.readLine()
    //R인 인덱스 기준으로 좌,우로 K의 개수 따로 저장
    //R의 개수만큼 leftK, rightK 저장됨
    val leftK = ArrayList<Int>()
    val rightK = ArrayList<Int>()
    var cnt = 0
    for (i in input.indices) {
        if (input[i] == 'K') cnt++
        else leftK.add(cnt)
    }
    cnt = 0
    for (i in input.length - 1 downTo 0) {
        if (input[i] == 'K') cnt++
        else rightK.add(cnt)
    }
    //rightK[0] == 맨 오른쪽 R 기준 오른쪽 K의 개수가 저장된 상태, 뒤집어서 LeftK와 맞춰주기
    rightK.reverse()

    //solve - twoPointer
    var s = 0
    var e = leftK.size - 1 // ==rifgtK.size-1
    var answer = 0
    while (s <= e) {
        //e-s+1 == 기준으로 잡은 e와 s 사이의 r개수
        //leftK[s].coerceAtMost(rightK[e]) == s와 e (왼쪽 R과 오른쪽 R)을 기준으로 했을 때 s 왼쪽 k 개수와 e 오른쪽 k 개수 중 작은 값
        answer = answer.coerceAtLeast((e - s + 1) + leftK[s].coerceAtMost(rightK[e]) * 2)
        if (leftK[s] < rightK[e]) s++
        else e--
    }
    //output
    write("$answer")

    close()
}