백준 20442번 ㅋㅋ루ㅋㅋ

http://icpc.me/20442

20442번: ㅋㅋ루ㅋㅋ

풀이

투 포인터를 이용하여 풀었습니다.

 

왼쪽에서 $i$번째 R을 기준으로 왼쪽에 있는 K의 수를 $lk[i]$, 오른쪽에 있는 K의 수를 $rk[i]$라고 하겠습니다. 

 

이때 $l$번째 R부터 $r$번째 R까지 사용한 ㅋㅋ루ㅋㅋ문자열의 최대 길이는 $r - l + 1 + 2\times min(lk[l], rk[r])$이 됩니다. R은 $r - l + 1$개, K는 왼쪽 오른쪽 각각 $min(lk[l], rk[r])$개씩 사용할 수 있기 때문입니다.

 

단순히 모든 가능한 $(l, r)$ 쌍에 대해 $l$번째 R부터 $r$번째 R까지 사용한 ㅋㅋ루ㅋㅋ 문자열의 길이 중 최댓값을 구하는 풀이는 $O(N^2)$로 시간초과일 것입니다. 투 포인터를 이용한다면 $O(N)$의 시간복잡도로 문제를 풀 수 있습니다.

 

만약 $lk[l]$ < $rk[r]$이라면 $r$을 아무리 줄여도 사용할 수 있는 K의 개수는 최대 $lk[l]$개이고, R의 개수만 계속 줄어들게 됩니다. 따라서 해당 경우에는 $l$을 1 증가시켜야 합니다. 마찬가지로 $lk[l]$ > $rk[r]$인 경우에는 $r$을 1 감소시켜야 합니다. 이를 이용하면 $l = 0$, $r = (R$의 수 $- 1)$으로 초기화하고 $l$과 $r$이 교차하기 전까지 $l, r$의 거리를 위 방식대로 좁혀가며 탐색할 수 있으며, 각 단계에서 구한 ㅋㅋ루ㅋㅋ 문자열의 최대 길이의 최댓값이 정답입니다.

 

 

코드

모든 $i$에 대해 $lk$, $rk$를 먼저 구해 준 뒤 투 포인터를 사용했습니다.

파이썬으로 풀었습니다.

import sys
 
s = sys.stdin.readline().strip()
lk = []
rk = []
cnt = 0
for i in s:
    if i == 'K':
        cnt += 1
    else:
        lk.append(cnt)
cnt = 0
for i in s[::-1]:
    if i == 'K':
        cnt += 1
    else:
        rk.append(cnt)
rk.reverse()
l, r = 0, len(lk) - 1
ans = 0
while l <= r:
    ans = max(ans, r - l + 1 + 2 * min(lk[l], rk[r]))
    if lk[l] < rk[r]:
        l += 1
    else:
        r -= 1
print(ans)

 

사족

며칠간 고민했지만 풀이를 떠올리지 못했는데, 알고리즘 분류를 보자마자 풀이가 생각났습니다.

KOI도 얼마 남지 않았는데 이상한 세그트리 풀지 말고 그리디/투 포인터 등 취약한 기초 부분을 연습해야 할 것 같습니다.

중간고사가 일주일도 채 남지 않았는데 몇 달만에 글을 새로 썼네요.