문제 소개
양의 정수로 이루어진 배열 nums가 주어졌을 때, k번 이상 반복되는 길이 m의 패턴이 존재하는지 확인해야 합니다. 여기서 패턴이란 하나 이상의 값으로 구성된 연속된 부분 배열이 여러 번 반복되는 형태를 의미하며, 패턴은 길이와 반복 횟수로 정의됩니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
- nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1]
- m = 3
- k = 2
이 경우 출력은 True입니다. 배열 안에 [1,4,3]이라는 패턴이 세 번 등장하기 때문입니다.
해결 접근 방법
이 문제는 리스트 슬라이싱(slicing)을 활용하면 매우 직관적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- i를 0부터 nums의 길이 - 1까지 순회합니다.
- sub1 := nums의 인덱스 i부터 (i + m*k - 1)까지의 부분 배열, 즉 길이가 m*k인 연속 구간
- sub2 := nums의 인덱스 i부터 (i + m - 1)까지의 부분 배열을 k번 이어 붙인 배열
- sub1과 sub2가 동일하다면 True를 반환합니다.
- 모든 시작 위치를 확인한 후에도 패턴을 찾지 못했다면 False를 반환합니다.
파이썬 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(nums, m, k):
for i in range(len(nums)):
# 길이 m*k만큼의 연속 구간 추출
sub1 = nums[i:i+m*k]
# 길이 m짜리 패턴을 k번 반복하여 생성
sub2 = nums[i:i+m]*k
if sub1 == sub2:
return True
return False
nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1]
m = 3
k = 2
print(solve(nums, m, k))입력
[3,5,1,4,3,1,4,3,1,4,3,9,6,1], 3, 2
출력
True
동작 원리 살펴보기
위 예제에서 i = 2일 때를 생각해 보겠습니다. nums[2:8]은 [1,4,3,1,4,3]이고, nums[2:5]*2 역시 [1,4,3,1,4,3]입니다. 두 배열이 완전히 일치하므로 함수는 즉시 True를 반환합니다. 이처럼 각 시작 위치에서 "연속 구간"과 "패턴의 k회 반복"을 단순 비교하는 것만으로 문제를 해결할 수 있습니다.
시간 및 공간 복잡도
각 시작 위치마다 최대 길이 m*k의 두 배열을 생성하고 비교하므로, n을 배열의 길이라 할 때 시간 복잡도는 O(n × m × k)입니다. 공간 복잡도는 비교용 임시 배열 때문에 O(m × k)입니다. 입력 크기가 크지 않다면 충분히 효율적인 방법이며, 코드가 간결하고 가독성이 높다는 장점이 있습니다.