문제 설명
2차원 배열 groups와 일반 배열 nums가 주어졌다고 가정해 보겠습니다. 우리가 확인해야 할 것은 nums 배열에서 서로 겹치지 않는 n개의 하위 배열을 순서대로 선택할 수 있는지 여부입니다. 이때 i번째 하위 배열은 groups[i](0-인덱스 기준)와 정확히 같아야 하며, i > 0인 경우 (i-1)번째 하위 배열이 nums에서 i번째 하위 배열보다 먼저 나타나야 합니다.
예를 들어, 입력이 다음과 같다고 해봅시다.
- groups = [[2,-2,-2],[4,-3,0]]
- nums = [1,-1,0,2,-2,-2,4,-3,0]
이 경우 출력은 True입니다. group[0]인 [2,-2,-2]는 nums의 인덱스 3부터 5까지 존재하고, group[1]인 [4,-3,0]은 인덱스 6부터 8까지 존재하며 두 하위 배열이 서로 겹치지 않고 순서도 올바르기 때문입니다.
해결 알고리즘
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 각 그룹을 nums에서 왼쪽부터 차례대로 찾고, 찾으면 그 위치 다음부터 다음 그룹을 탐색하면 됩니다. 구체적인 단계는 다음과 같습니다.
- 탐색 시작 위치 i를 0으로 초기화합니다.
- groups의 각 grp에 대해 다음을 수행합니다.
- j를 i부터 nums의 마지막 인덱스까지 반복합니다.
- 만약 nums[j]부터 nums[j + len(grp)]까지의 하위 배열이 grp와 같다면:
- i를 j + len(grp)로 갱신합니다.
- 내부 루프를 빠져나가 다음 그룹을 탐색합니다.
- 끝까지 탐색했는데도 grp를 찾지 못했다면:
- False를 반환합니다.
- 모든 그룹을 성공적으로 찾았다면 True를 반환합니다.
구현 예제
더 잘 이해하기 위해 다음 Python 코드를 살펴보겠습니다.
def solve(groups, nums):
i = 0
for grp in groups:
for j in range(i, len(nums)):
if nums[j:j+len(grp)] == grp:
i = j + len(grp)
break
else:
return False
return True
groups = [[2,-2,-2],[4,-3,0]]
nums = [1,-1,0,2,-2,-2,4,-3,0]
print(solve(groups, nums))입력
[[2,-2,-2],[4,-3,0]], [1,-1,0,2,-2,-2,4,-3,0]
출력
True
복잡도 분석
시간 복잡도는 최악의 경우 O(n × m × k)입니다. 여기서 n은 nums의 길이, m은 groups의 개수, k는 각 그룹의 평균 길이입니다. 공간 복잡도는 슬라이싱 비교 시 O(k)의 추가 공간이 사용될 수 있습니다.