소문자로만 이루어진 문자열 s가 주어졌을 때, 다음 두 조건을 동시에 만족하는 부분 수열(subsequence)을 선택할 수 있는지 판별하는 문제입니다.
- 선택된 문자들의 인접한 인덱스 차이가 모두 같아야 합니다(등차 간격).
- 선택된 문자들을 순서대로 이어 붙이면 "programmingquestion"이라는 문자열이 되어야 합니다.
예를 들어 입력 문자열이 "pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"이라면 출력 결과는 True입니다.
문제 해결 접근 방법
"programmingquestion"은 첫 두 글자가 'p'와 'r'이므로, 먼저 문자열에서 'p'와 'r'이 등장하는 위치들을 모두 찾습니다. 그다음 가능한 모든 ('p', 'r') 위치 조합에 대해 간격을 정하고, 해당 간격으로 문자를 건너뛰며 읽었을 때 목표 문자열이 만들어지는지 확인합니다. 구체적인 단계는 다음과 같습니다.
- p := 문자열에서 'p'가 나타나는 모든 인덱스의 배열
- r := 문자열에서 'r'이 나타나는 모든 인덱스의 배열
- p의 각 인덱스 j와 r의 각 인덱스 k에 대해, k > j인 경우:
- s[j]부터 문자열 끝까지 (k − j) 간격으로 건너뛰며 추출한 부분 문자열에 "programmingquestion"이 포함되어 있으면 True를 반환합니다.
모든 조합을 확인한 후에도 조건을 만족하는 경우가 없다면 False를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, s):
p = [i for i, c in enumerate(s) if c == "p"]
r = [i for i, c in enumerate(s) if c == "r"]
for j in p:
for k in r:
if k > j:
if "programmingquestion" in s[j:len(s):k-j]:
return True
return False
ob = Solution()
s = "pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"
print(ob.solve(s))입력
"pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"
출력
True
코드 설명
핵심은 파이썬의 슬라이싱 문법 s[j:len(s):k-j]입니다. 이 표현식은 인덱스 j부터 시작해 매번 (k − j)씩 건너뛰며 문자를 추출합니다. 즉, 첫 글자 'p'(인덱스 j)와 두 번째 글자 'r'(인덱스 k) 사이의 거리가 곧 전체 부분 수열의 공통 간격이 됩니다. 따라서 슬라이싱 결과에 "programmingquestion"이 그대로 포함되어 있다면, 등차 간격 조건을 만족하는 부분 수열이 존재한다는 의미입니다.