투포인터(백준 알고리즘 20442번)

♣ 문제 이해

 

 

위의 문제는 K와 R로만 이뤄진 문자열이 주어졌을 때 'R'로만 이뤄진 문자열, 또는 양끝에 같은 수의 K를 가지고, 가운데에는 R들이 올 수 있는 문자열 중 가장 긴 문자열의 길이를 출력하는 문제이다. 

 

또한 힌트에 의하면 문자열에서 몇 개의 문자를 지워서 부분 문자열을 만드는 것도 가능하다. 

 

 

예제를 보면 ㅋㅋ루ㅋㅋ 문자열의 조건을 만족하는 문자열은 아래와 같다. 

 

R, KRK, KKRKK

 

이 중 가장 긴 문자열의 길이는 5이다. 

 

 

두 번째 예제를 보면 조건을 만족하는 문자열은 아래와 같다. 

R, RR, RRR, RRRR

 

K가 R의 양쪽에 같은 갯수만큼 와야 하는데 그게 불가능하기 때문에 가운데 K를 지워버리고 R을 모두 붙여서 ㅋㅋ루ㅋㅋ 문자열을 만드는 게 더 최대의 길이를 구하는 경우이다. 

 

♣ 문제 해결 방식

1. 문자열 순회하여 R의 인덱스, 해당 r이 가지는 왼쪽과 오른쪽 K의 개수 구하기

 

이 문제는 투포인터를 이용하여 주어진 문자열을 순회하면서 R의 위치와 해당 R의 위치에서 왼쪽과 오른쪽에 올 수 있는 K의 길이를 저장하였다. ㅋㅋ루ㅋㅋ 문자열은 반드시 R을 포함해야 하므로 R의 위치를 이용하여 문자열에 R이 포함될 수 있도록 하는 것이다. 

 

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

sentence = input()
start, end = 0, len(sentence)-1
left, right = 0, 0
r = []
left_k = [0]*len(sentence)
right_k = [0]*len(sentence)

 

sentence로 주어진 문자열을 받는다. start와 end는 R의 위치를 표시하기 위해 문자열을 순회할 때 사용하는 투포인터의 시작과 끝을 의미한다. start는 문자열의 맨 앞에서 점차 늘어나면서, end는 문자열의 맨 뒤에서 점차 줄어들면서 문자열을 순회한다. 이때 start에 해당하는 위치의 왼쪽에 있는 K의 수를 left에 저장하고, end에 해당하는 위치의 오른쪽에 있는 K의 수를 right에 저장한다. 그리고 R이 나올 때마다 r에 해당 인덱스를 저장하고, 해당 R의 입장에서 보았을 때의 K의 수를 left_k 또는 right_k 에 저장한다. 코드로 나타내면 아래와 같다. 

 

for i in range(len(sentence)):
	if sentence[start] == 'K':
		left +=1 
	else:
		r.append(start)
		left_k[start] = left 
	start +=1 
	
	if sentence[end] == 'K':
		right +=1 
	else:
		r.append(end)
		right_k[end] = right
	end -= 1
    
r = sorted(set(r))
r = list(r)

 

문자열이 KKRKKRRKR 이라고 해보자. 위의 코드를 표로 나타내면 아래와 같다. 

start	0	1	2	3
end	8	7	6	5
left	1	2	2	3
right	0	1	1	1
left_k	[0, 0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 2, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 1, 1, 0, 0]
right_k	[0, 0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 1, 0, 0]	[0, 0, 2, 0, 0, 0, 0, 0, 0]
r	[8]	[8]	[8, 2, 6]	[8, 2, 6, 5]

 

start	4	5	6	7	8
end	4	3	2	1	0
left	4	4	4	5	5
right	2	3	3	4	5
left_k	[0, 0, 2, 0, 0, 0, 0, 0, 0]	[0, 0, 2, 0, 0, 4, 0, 0, 0]	[0, 0, 2, 0, 0, 4, 4, 0, 0]	[0, 0, 2, 0, 0, 4, 4, 0, 0]	[0, 0, 2, 0, 0, 4, 4, 0, 5]
right_k	[0, 0, 0, 0, 0, 1, 1, 0, 0]	[0, 0, 0, 0, 0, 1, 1, 0, 0]	[0, 0, 3, 0, 0, 1, 1, 0, 0]	[0, 0, 3, 0, 0, 1, 1, 0, 0]	[0, 0, 3, 0, 0, 1, 1, 0, 0]
r	[8, 2, 6, 5]	[8, 2, 6, 5, 5]	[8, 2, 6, 5, 5, 6, 2]	[8, 2, 6, 5, 5, 6, 2]	[8, 2, 6, 5, 5, 6, 2, 8]

 

표를 보면 left와 right를 이용하여 left_k와 right_k를 채워넣었다. 순회가 끝난 마지막 결과물에서 left_k와 right_k, r이 중요하다. start와 end가 동시에 문자열을 순회하기 때문에 r에 R의 인덱스가 두 번씩 저장된다. 따라서 r 의 중복된 요소들을 제거하고 sorted를 이용하여 정렬한다. 

r = [2, 5, 6, 8]
left_k = [0, 0, 2, 0, 0, 4, 4, 0, 5]
right_k = [0, 0, 3, 0, 0, 1, 1, 0, 0]

 

KKRKKRRKR 에서 R의 인덱스는 2, 5, 6, 8이다. left_k 와 right_k 를 보면 R의 인덱스에 해당하는 2, 5, 6, 8 에만 숫자가 있다.  index 2에 해당하는 R의 입장에서 봤을 때 left_k[2] = 2 이므로 왼쪽에 K가 2개 있다는 것을 의미한다. 또한 right_k[2] = 3 이므로 오른쪽에 K가 3개라는 것이다. 

 

index 5, 6, 8에 해당하는 left_k, right_k 의 숫자들 역시 마찬가지이다. 

 

 

2. R의 위치를 투 포인터로 탐색하여 최대 길이의 문자열 구하기 

위의 코드에서 R의 위치와 각 R의 입장에서 봤을 때 왼쪽과 오른쪽에 있는 K의 수를 구하였다. 이를 이용하여 최대 길이의 문자열을 구할 수 있다. 

#투 포인터 방식으로 최대 길이 구하기
left = 0 
right = len(r)-1
result = 0 

while left <= right:
	#r을 기준으로 했을 때 왼쪽과 오른쪽 k의 개수
	left_cnt = left_k[r[left]]
	right_cnt = right_k[r[right]]
	# print(left_cnt, right_cnt)
	
	#가운데 R의 개수와 양쪽 k의 개수를 고려하기 
	result = max(result, (right-left+1)+min(left_cnt, right_cnt)*2)
	
	#왼쪽의 k가 많으면 오른쪽 포인터 움직이기
	if left_cnt > right_cnt:
		right-=1 
	else:
		left +=1

 

left 와 right는 R의 위치를 투포인터로 탐색하는 데 사용하는 변수이다. left는 왼쪽부터 탐색하기 때문에 0, right는 오른쪽부터 탐색하기 때문에 len(r) -1 로 정의된다. result 에는 가장 긴 문자열의 길이를 담을 예정이다. 

 

while문을 사용하여 left가 right보다 값이 작거나 같을 때까지만 탐색을 진행한다. left_cnt는 각각 left, right의 R을 기준으로 했을 때 왼쪽에 있는 K의 수, right_cnt는 오른쪽에 있는 K의 수를 의미한다. 

 

result를 보면, 현재의 result 값과 (right-left+1)+min(left_cnt, right_cnt)*2 중 최댓값을 구해서 result에 다시 넣는다.

(right-left+1)+min(left_cnt, right_cnt)*2

 

위의 공식에서 right - left + 1 은 가운데 올 수 있는 R의 개수를 뜻한다. 예를 들어 left = 0, right = 3 일 때, 이 둘은 각각 맨 앞에 있는 R의 위치와 맨 끝에 있는 R의 위치를 의미한다. 그리고 이 사이에는 1, 2 인덱스에 해당하는 R이 2개 더 있다. 따라서 right - left + 1 = (3 - 0 ) + 1 = 4 이므로 현재 탐색하고 있는 위치에서 보면 가운데 있을 수 있는 최대 R의 개수가 4개라는 것을 알 수 있다. 

left_cnt 는 left 에 해당하는 R의 왼쪽에 올 수 있는 K의 수이다. right_cnt 는 right 에 해당하는 R의 오른쪽에 올 수 있는 K의 수이다. 

 

KKR(left, 0)KKRRKR(right, 3) 

 

이때 left_cnt = 2(left 에 해당하는 R의 왼쪽에 K가 2개이므로), right_cnt = 0(right 에 해당하는 R의 오른쪽에 K 가 0개이므로). 그런데 K는 ㅋㅋ루ㅋㅋ 문자열의 양쪽에 같은 수만큼 있어야 하므로 둘 중 작은 값에 2를 곱한 값이 K의 갯수가 되는 것이다. 이렇게 구한 R의 개수와 K의 개수를 더하면 ㅋㅋ루ㅋㅋ 문자열의 길이를 구할 수 있다. 

 

마지막으로 K의 수를 최대한 맞추기 위해서 왼쪽의 K가 많으면 오른쪽 포인터를 늘리고, 오른쪽의 K가 많으면 왼쪽의 포인터를 줄여서 탐색을 진행한다. 

left	0	0	0	0
right	3	2	1	0
left_cnt	2	2	2	2
right_cnt	0	1	1	3
result	4	5	5	5

 

이렇게 답을 구할 수 있긴 하지만 처음에 순회를 쭉 하고 R의 위치를 한 번 더 순회하기 때문에 시간이 오래 걸린다.