[Python/파이썬] 백준 20442번 ㅋㅋ루ㅋㅋ

20442번: ㅋㅋ루ㅋㅋ

 

문제

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

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

 

 

입력

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

출력

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

코드

input_str = input()

# k, r 개수 누적합
cnt_k = [0] * (len(input_str)+1)
cnt_r = [0] * (len(input_str)+1)
for i in range(1, len(input_str)+1):
    if input_str[i-1] == 'K':
        cnt_k[i] = cnt_k[i-1] + 1
        cnt_r[i] = cnt_r[i-1]
    else:
        cnt_k[i] = cnt_k[i-1]
        cnt_r[i] = cnt_r[i-1] + 1
# 부분 수열 중 ㅋㅋ루ㅋㅋ 문자열이 없는 경우
if cnt_r[-1] == 0:
    print(0)
    exit()
# 투포인터
ans = 0
start, end = 0, len(input_str)-1
while start <= end:
    # R 찾기
    while start < len(input_str) and input_str[start] != 'R':
        start += 1
    while end > 0 and input_str[end] != 'R':
        end -= 1
    # ㅋㅋ루ㅋㅋ 문자열 길이 구하기
    left_k = cnt_k[start]
    right_k = cnt_k[len(input_str)]-cnt_k[end+1]
    r_len = cnt_r[end+1]-cnt_r[start]
    if left_k > right_k:
        ans = max(ans, right_k*2 + r_len)
        while end > 0 and input_str[end] == 'R':
            end -= 1
    else:
        ans = max(ans, left_k*2 + r_len)
        while start < len(input_str) and input_str[start] == 'R':
            start += 1

print(ans)

먼저 문자열 길이를 빠르게 구하기 위해 cnt_k, cnt_r 배열에 각각 K와 R의 개수의 누적합을 구해둔다.

이때 cnt_r의 마지막 원소가 0이라면 이 배열에는 R이 존재하지 않는 것이므로 부분 수열 중 ㅋㅋ루ㅋㅋ인 문자열이 없다는 뜻이다. 따라서 이 경우 0을 출력하고 프로그램을 종료한다.

 

투포인터를 이용하여 문제를 해결해볼 것이다.

1. R의 시작과 끝 인덱스를 찾아서 각각 start, end 변수에 저장한다.
2. start와 end 인덱스 사이의 R만 존재하는 부분 수열의 길이(r_len)를 구한다. start 왼쪽 부분 수열에 존재하는 K의 개수(left_k)와 end 오른쪽 부분 수열에 존재하는 K의 개수(right_k) 중 더 작은 값이 지금 구하는 ㅋㅋ루ㅋㅋ 문자열 양옆에 달릴 수 있는 K의 개수이다. 그러므로 이때 둘 중 더 작은 값을 2배한 값 + r_len이 현재 보고 있는 부분의 ㅋㅋ루ㅋㅋ 부분 수열의 최대 길이이다.
3. K의 개수가 더 적은 쪽의 인덱스를 조정해서 K의 길이가 더 길어지도록 한다.