문제 설명
오색사탕은 길이 1 cm마다 빨강(R), 노랑(Y), 초록(G), 파랑(B), 보라(P)의 다섯 가지 색깔 중 하나로 구성되어 있습니다. 사람들은 오색사탕을 먹으면 행운이 온다고 믿으며, 길이에 상관없이 사탕의 “양쪽 끝의 동일한 부분”이 많을수록 더 많은 행운을 가져다 준다고 믿습니다. “양쪽 끝의 동일한 부분”이란 사탕 앞부분의 왼쪽부터 X cm와 사탕 끝부분의 왼쪽부터 X cm의 색 순서가 동일한 경우를 말합니다.
예를 들어 사탕의 앞부분이 왼쪽부터 빨강, 노랑, 파랑으로 시작하고 끝부분도 왼쪽부터 빨강, 노랑, 파랑으로 끝나면, 양쪽 끝의 동일한 부분입니다.
아래 그림 1과 같이 오색사탕이 [빨강, 노랑, 빨강, 노랑, 빨강]으로 구성되었을 경우, 양쪽 끝의 동일한 부분은 다음과 같이 두 가지 입니다.
[빨강] - 1 cm 구간과 5 cm 구간의 색 순서가 동일합니다.
[빨강, 노랑, 빨강] - 1 ~ 3 cm 구간과 3 ~ 5 cm 구간의 색 순서가 동일합니다.
1 ~ 2 cm 구간 [빨강, 노랑]과 4 ~ 5 cm 구간 [노랑, 빨강]은 색의 순서가 동일하지 않으므로 양쪽 끝의 동일한 부분이 아닙니다. 또한, 오색사탕 전체는 양쪽 끝이 항상 동일하므로 동일한 부분으로 세지 않습니다. 즉, [빨강, 노랑, 빨강, 노랑, 빨강] 전체는 제외합니다.
사탕 공장 사장은 긴 오색사탕을 만든 후 절단해서 판매하려고 합니다. 이때 "양쪽 끝의 동일한 부분"이 많을 수록 가격이 비싸지므로, 먼저 특정 위치에서 사탕을 절단했을 때 양쪽 끝의 동일한 부분의 수를 파악하려 합니다. 오색사탕을 절단할 때는 항상 사탕의 맨 왼쪽을 기준으로 정수단위(cm)만큼 떨어진 위치에서 절단합니다.
예를 들어, 아래 그림 2의 오색사탕을 위치 5에서 절단한다면 위의 그림 1과 같이 양쪽 끝의 동일한 부분이 2개 있으며, 위치 12에서 절단한다면, 양쪽 끝의 동일한 부분들이 [빨강], [빨강, 노랑, 빨강], [빨강, 노랑, 빨강, 노랑, 빨강]으로 3개 있습니다.
오색사탕 candy와 절단할 위치들의 집합 positions가 주어졌을 때, 각 위치마다 양쪽 끝의 동일한 부분들의 수를 return하는 solution 함수를 완성해주세요.
제한사항
7 ≤ candy의 길이 ≤ 1,000,000
3 ≤ positions의 길이 ≤ 100
positions의 각 원소는 candy의 길이 이하인 자연수이며 중복되지 않습니다.
각 색깔은 다음과 같이 하나의 문자로 나타냅니다.
candy의 원소는 'R', 'Y', 'G', 'B', 'P'로만 이루어져 있습니다.
색깔 문자
빨강 ‘R’
노랑 ‘Y’
초록 ‘G’
파랑 ‘B’
보라 ‘P’
입출력 예
candy positions result
“RYRYRGPRYRYRBB” [12, 1, 14, 7] [3, 0, 0, 0]
“BPBRBPBRB” [3, 6, 9] [1, 1, 2]입출력 예 #1
위치 12에서 절단한 경우, 문제의 그림 2 예제와 같습니다.
위치 1에서 절단한 경우, 절단된 오색사탕은 “R” 입니다. 절단된 사탕 전체는 양쪽 끝의 동일한 부분으로 세지 않기 때문에 0입니다.
위치 14에서 절단한 경우, 절단된 오색사탕은 “RYRYRGPRYRYRBB” 입니다. 양쪽 끝의 동일한 부분이 없기 때문에 0입니다.
위치 7에서 절단한 경우, 절단된 오색사탕은 “RYRYRGP” 입니다. 양쪽 끝의 동일한 부분이 없기 때문에 0입니다.
그러므로 [3, 0, 0, 0]을 return합니다.
입출력 예 #2
위치 3에서 절단한 경우, 절단된 오색사탕은 “BPB” 입니다. 양쪽 끝의 동일한 부분은 “B”만 존재하므로 1입니다.
위치 6에서 절단한 경우, 절단된 오색사탕은 “BPBRBP” 입니다. 양쪽 끝의 동일한 부분은 “BP”만 존재하므로 1입니다.
위치 9에서 절단한 경우, 절단된 오색사탕은 “BPBRBPBRB” 입니다. 양쪽 끝의 동일한 부분은 “B”, ”BPBRB”가 존재하므로 2입니다.
그러므로 [1, 1, 2]를 return합니다.
def solution(candy, positions):
# part1
n_match, cache = 0, [0]*len(candy)
for i in range(1, len(candy)):
while n_match and candy[n_match] != candy[i]:
print('while i ===>',i)
n_match = cache[n_match]
if candy[n_match] == candy[i]:
print('if i ====>',i)
n_match += 1
cache[i] = n_match
print(cache)
# part2
answer = []
for pos in positions:
ans = 0
while cache[pos-1]:
print('pos ===>',pos)
pos = cache[pos-1]
ans += 1
answer.append(ans)
return answer