[백준 - Python] 20442 - ㅋㅋ루ㅋㅋ

0.  문제 링크

 

 

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

20442번: ㅋㅋ루ㅋㅋ

---

1.  풀이 방법

 

 

https://chanu-ps.tistory.com/24

우선 위의 블로그를 참고하였습니다.

맨 처음에 원포인터로 각 R의 위치에서 양 옆의 K의 개수를 세서 구하는 식으로 했는데, 예제랑 질문 게시판의 반례도 다 맞았는데도 1% 펑하길래 좀 힘들었습니다.

혼자 막 도전하다가 결국 구글링을 했는데, 위의 블로그가 매우 잘 정리해놓았습니다.

 

그래도 혹시 문제가 이해 안 간다던가 풀이가 이해가 안 가는 사람을 위해 설명을 해놓겠습니다.

문제는 문자열에서 부분 수열을 뽑아야 하는데, KRK가 있다면 부분 수열은 KRK, KR, RK, KK, K, R, K, ''이 될 수 있습니다.

두 번째로 R로만 이루어진 문자열은 ㅋㅋ루ㅋㅋ가 된다고 했는데, RR도 되고, RRRR도 됩니다. 다만 중간에 K가 끼면 안 됩니다.

RRKRR은 ㅋㅋ루ㅋㅋ가 될 수 없습니다.

세 번째 조건은 ㅋㅋ루ㅋㅋ 문자열 양 끝의 K 또한 ㅋㅋ루ㅋㅋ가 된다고 했는데, 이는 R로만 이루어진 문자열의 양 끝에 K가 붙어야 된다는 의미입니다. 그것도 동일한 개수로

따라서 KKRKK도 가능하고, KRRRRRK도 가능합니다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    maps = list(input().strip())

    left_cnt, right_cnt = [], []

    # K의 개수를 세서 각 R의 자리에 넣어줌
    cnt = 0
    for i in maps:
        if i == 'K':
            cnt += 1
        else:
            left_cnt.append(cnt)

    cnt = 0
    for i in maps[::-1]:
        if i == 'K':
            cnt += 1
        else:
            right_cnt.append(cnt)
    right_cnt.reverse()

    left = 0
    right = len(right_cnt) - 1
    ans = 0

    while left <= right:
        ans = max(ans, right - left + 1 + min(left_cnt[left], right_cnt[right]) * 2)
        # 구간에서 R의 개수는 right - left + 1이고, 바깥의 K의 개수는 위의 min(~~) * 2개임
        if left_cnt[left] < right_cnt[right]:
            left += 1
        elif left_cnt[left] > right_cnt[right]:
            right -= 1
        else:
            left += 1
            right -= 1

    print(ans)

---

3.  마무리