[백준 20442번] ㅋㅋ루ㅋㅋ (Python3)

import sys
input = sys.stdin.readline

seq = input().strip()
l = len(seq)

cntR = []
Rexist = 0
start,end = 0,l-1
while True:
  cntR.append(0)
  if start == end:
    if seq[start] == "R":
      Rexist = len(cntR)
      cntR[-1] += 1
    break
  while seq[start] == "R":
    Rexist = len(cntR)
    cntR[-1] += 1
    if start == end:
      break
    start += 1
  if start == end:
    break
  while seq[end] == "R":
    Rexist = len(cntR)
    cntR[-1] += 1
    end -= 1
  if end-start <= 1:
    break
  start += 1
  end -= 1

L = Rexist
SUM = [0] * L
s = 0
for i in range(1,L+1):
  s += cntR[L-i]
  SUM[L-i] = s

for i in range(L):
  SUM[i] += i*2

if not SUM:
  print(0)
else:
  print(max(SUM))

 

전형적인 투 포인터 문제였다.

간단하게 요약하면,

1. 맨 처음과 끝에서 투 포인터로 시작.

2. 현 위치가 R인 경우 cntR 리스트에 R의 개수를 저장해주고, K를 만날때까지 이동

3. start와 end가 모두 K에 도착하면 리스트 원소를 하나 추가하고 start,end를 한칸씩 이동

4. start와 end가 만날때까지 2~3번 반복

5. cntR 리스트의 누적합을 구하고, K가 2개씩 반복되므로 각 항마다 2를 더해준 뒤, 최댓값 출력

 

이때 놓치기 쉬운 포인트는

1. 빈 리스트는 ㅋㅋ루ㅋㅋ가 아니기 때문에 R이 존재하는지 여부를 저장해주어야한다. (Rexist)

2. ㅋㅋ루ㅋㅋ 문자열이 1개도 없는 경우에 0을 출력해주어야한다.

 

 

오늘의 교훈) 0인 경우를 빼먹지 말자