백준 20442 - ㅋㅋ루ㅋㅋ

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

풀이

문자열 S가 주어졌을 때, ㅋㅋ루ㅋㅋ의 형태를 만들 수 있는 가장 긴 부분 문자열의 길이를 구하는 문제이다.

“ㅋㅋ루ㅋㅋ” 형태는 양 끝에는 K가 존재해야하며, 그 사이에 있는 R의 개수가 최대가 되어야 한다.

접근 방식

필자는 문제 접근에서 투포인터 기법을 활용해서 해결했다.

1. 초기 데이터 수집
   1. K와 R의 개수를 미리 세어둔다.
   2. num_k, num_r 을 통해 K와 R의 개수를 따로 저장한다.
2. 투 포인터 설정
   1. start = -1 (즉, 왼쪽에서 K를 찾을 위치)
   2. end = len(S) (즉, 오른쪽에서 K를 찾을 위치)
   3. max_length = 0 (만들 수 있는 최대 부분 문자열의 길이)
3. 투 포인터 탐색
   1. K가 양 끝에 i개씩 있는 경우를 고려해여 2 * i + num_r 로 가능한 최대 길이를 갱신한다.
   2. start와 end를 점진적으로 이동시키며 K의 위치를 조정한다.
   3. K가 아닌 문자를 건너뛰면서 num_r의 개수를 줄인다.

start = -1
end = len(S)
max_length = 0

for i in range(num_k // 2 + 1) :
    if num_r == 0 :
        break

    # 앞, 뒤로 K가 i개씩 있는 경우
    max_length = max(max_length, 2 * i + num_r) 

    start += 1
    end -= 1
    while start < end and S[start] != 'K' :
        start += 1
        num_r -= 1
    while start < end and S[end] != 'K'  :
        end -= 1
        num_r -= 1

K의 절반 개수 (num_k // 2) 만큰 반복하면서 투 포인터를 이동시킨다.

2 * i + num_r로 현재 K 개수를 기반으로 가능한 최대 길이를 계산한다.

start와 end를 움직이며 K를 찾고, K가 아닌 문자(R)을 빼면서 남은 R의 개수를 조절한다.

시간 복잡도 분석

1. num_k // 2 만큼 루프가 진행되고, 내부에서, start와 end가 가각 문자열을 탐색하기 때문에 O(N)과 근접하다.
2. 문자열을 한 번 순회하며, K, R을 세는 과정도 O(N)이다.
3. 즉, O(N)에 근접한 시간 복잡도를 가진다.

코드

# 백준 20442 - ㅋㅋ루ㅋㅋ
# 분류 : 문자열, 투 포인터

S = input()

num_k = 0
num_r = 0

for i in range(len(S)) :
    if S[i] == 'K' :
        num_k += 1
    if S[i] == 'R' :
        num_r += 1

start = -1
end = len(S)

max_length = 0

for i in range(num_k // 2 + 1) :
    if num_r == 0 :
        break

    # 앞, 뒤로 K가 i개씩 있는 경우
    max_length = max(max_length, 2 * i + num_r) 

    start += 1
    end -= 1
    while start < end and S[start] != 'K' :
        start += 1
        num_r -= 1
    while start < end and S[end] != 'K'  :
        end -= 1
        num_r -= 1
    
print(max_length)