백준 20442 ㅋㅋ루ㅋㅋ (파이썬)

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

20442번: ㅋㅋ루ㅋㅋ

풀이

문제를 처음 보았을때 DP를 이용해 문제를 푸는건가 싶어 이리저리 생각을 해보았지만 마땅한 해결책이 나오지 않아 다른 분이 푸신 것을 참고하여 풀었습니다. 

참고한 블로그 글

해당 문제는 투 포인터를 이용해서 푸는 문제였습니다. 그러나 저는 투 포인터에 대해 몰랐기에 나동빈님의 강의 영상을 보고 투 포인터에 대한 개념을 잡고 다른 분이 푸신 것을 참고하여 이해하고 풀었습니다.

강의 링크

 

이미 참고한 블로그 글에서 자세히 설명이 되어 있지만 분명 투 포인터에 대한 개념없이 문제를 접근하신분들도 있을거라 생각이 들기에 투포인터를 처음 접한 사람의 입장에서 더 자세하게 풀이법을 작성하고자 합니다.

1. 문제에서 주어진 부분 문자열은 다음과 같이 만들수 있습니다.
   • 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다.
2. 그리고 문자 'K'는 없어도 "ㅋㅋ루ㅋㅋ"문자열이 성립되지만 'R'은 하나 이상 존재해야 합니다.
3. 그렇기 때문에 문자 R을 기준으로 왼쪽에 존재하는 문자 'K'의 개수를 저장하는 배열 lk, 오른쪽에 존재하는 문자 'R'을 저장하는 배열 rk를 만듭니다.
4. 문자 'R'을 가리키는 변수 l, r을 생성하고 lk혹은 rk 배열의 길이를 r에 할당합니다. (인덱스라고도 생각하셔도 좋습니다.)
5. l<=r 이라는 조건이 참일때 문자열의 최대값을 구합니다.
   • 이때 최대값을 구하는 공식은 (r-l+1) + 2*min(lk[l], rk[r])입니다.
   • 저는 여기서 2*min(lk[l], rk[r])은 문자 'R'양 옆에 존재하는 'K'의 개수를 구하는 코드라는 것은 쉽게 이해하였으나 (r-l+1)이 쉽게 이해가지 않았습니다. (만약 중간에 존재하는 문자열이 'ㅋㅋ루ㅋㅋ'를 만족하지 못하지 않을까? 라는 생각때문이였습니다.)
   • 그러나 r과l이 가지는 의미에 대해서 생각을 해보니 쉽게 문제가 해결되었습니다. 
     
     • 각 문자들이 가지는 의미는 전체 문자에서 'R'의 순서였기 때문에 r-l+1은 r과 l사이에 존재하는 r로만 이루어진 문자열의 길이입니다. 그렇기에 r-l+1의 길이를 가지는 문자열은 무조건 ㅋㅋ루ㅋㅋ를 만족하게 됩니다.

 

코드

import sys

input = lambda: sys.stdin.readline().rstrip()

s = input()
lk, rk = [], []

cnt = 0
for c in s:
    if c == 'K':
        cnt += 1
    else:
        lk.append(cnt)

cnt = 0
for c in s[::-1]:
    if c == '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)

 

덕분에 "투포인터" 알고리즘에 대해 배울수 있었으며 응용까지 할 수 있었던 문제였습니다.