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

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

20442번: ㅋㅋ루ㅋㅋ

재밌는 문제 이름을 찾다가 ㅋㅋ루ㅋㅋ를 발견하여 바로 풀기 시작했다.

왼쪽과 오른쪽 끝부터 가운데로 오면서 K의 개수를  세다가 R을 만나면 적은 K의 개수를 2배+1 하고 R의 개수를 더한다.

 

예를 들어 K R K K R K R R R K K K R K K 가 있다면 양쪽 끝부터 k의 개수를 센다.왼쪽에서 첫번째 R은 1번째 인덱스에 있고 오른쪽에서 첫번째 R은 -3번째 인덱스에 있다.

K R K K R K R R R K K K R K K

왼쪽 R 까지의 K의 개수는 1개이고, 오른쪽 R까지의 K의 개수는 2개이다. 따라서 가능한 ㅋㅋ루ㅋㅋ문자열의 길이는 3 + R의 개수다.왼쪽 K의 개수가 더 작으므로 왼쪽을 다음 R이 나올때까지 탐색해준다. 왼쪽이 줄어들었으니 R의 개수는 하나 줄여줘야하고, 다시 K의 개수를 세준다.

K R K K R K R R R K K K R K K 이런식으로 반복하면서 ㅋㅋ루ㅋㅋ 문자열이 가능한 경우를 구하면된다.

K R K K R K R R R K K K R K K, K R K K R K R R R K K K R K K ....

 

양쪽에서 줄어들때마다 R의 개수를 하나씩 빼주면된다. 양쪽 K의 개수가 같아서 둘다 줄어든다면 당연히 2 개를 빼주면 된다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
def Sol():
  jammin = list(input().rstrip())
  r_count = 0
  k_count = []
  r_pos = []
  total_k = 0

  for i in range(len(jammin)):
    if jammin[i] == 'R':
      r_count += 1
      r_pos.append(i)
      k_count.append(i-r_count + 1)
    else:
      total_k += 1

  if r_count == 0:
    print(0)
    sys.exit()


  max_zzfzz = 0
  ## 투 포인터 변수
  i, j = 0, -1
  
  left = r_pos[i]
  right = r_pos[j]
  while left <= right:
    left_k = k_count[i]
    right_k = total_k - k_count[j]
    max_zzfzz = max(max_zzfzz, min(left_k, right_k)*2 + r_count)
    if left_k > right_k:
      j -= 1
      r_count -= 1
    elif left_k < right_k:
      i += 1
      r_count -= 1
    else:
      i += 1
      j -= 1
      r_count -= 2
      
    ## 탐색하다보면 INDEX_ERROR가 뜰 수도 있는데 try-except문으로 처리해주었다.
    try:
      left = r_pos[i]
      right = r_pos[j]
    except:
      break
  print(max_zzfzz)

if __name__ == "__main__":
  Sol()

 

 

풀긴했는데 진짜 못짠 코드 같다. 나중에 실력이 오르고 보면 웃을거 같은 느낌...

그리고 문제 출처를 보니 학교 선배님이 만드신 문제더라...ㅋㅋ

 

글에대한 질문과 코드에 대한 조언 모두 환영합니다!