모든 요소가 고유한 배열 nums와, 여러 개의 작은 배열들을 담고 있는 또 다른 배열 pieces가 있다고 가정해 보겠습니다. 이때 pieces에 포함된 배열들을 임의의 순서로 이어 붙여(concatenate) 원래 배열 nums를 만들 수 있는지 확인해야 합니다.
단, 중요한 제약 조건이 하나 있습니다. 각 조각 pieces[i] 내부에 있는 요소들의 순서는 절대 변경할 수 없다는 것입니다. 즉, 조각 자체를 회전하거나 뒤집는 것은 허용되지 않으며, 조각들을 배치하는 순서만 자유롭게 정할 수 있습니다.
예제
입력이 다음과 같다고 해보겠습니다.
nums = [5,1,12,36,2,47,6] pieces = [[2,47,6],[12,36],[1],[5]]
이 경우 출력은 True입니다. 왜냐하면 조각들을 [[5], [1], [12,36], [2,47,6]] 순서로 이어 붙이면 원래 배열 nums를 정확히 만들 수 있기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
결과를 저장할 빈 리스트
temp를 생성합니다.pieces의 각 조각p에 대해 다음을 반복합니다.p[0](조각의 첫 번째 요소)이nums에 존재하지 않으면False를 반환합니다.l을 조각p의 길이로 설정합니다.indx를nums에서p[0]의 인덱스로 설정합니다.nums[indx]부터nums[indx+l-1]까지의 부분 배열이 조각p와 일치하지 않으면False를 반환합니다.일치한다면 조각
p를temp에 추가합니다.
모든 조각을 처리한 후,
temp의 길이가nums의 길이와 같으면True를, 그렇지 않으면False를 반환합니다.
이 방법이 작동하는 핵심 이유는 모든 요소가 고유하기 때문입니다. 요소가 고유하므로 각 조각의 첫 번째 값이 nums에서 나타나는 위치는 유일하며, 그 위치부터 시작하는 연속된 구간이 조각과 정확히 일치하는지만 검사하면 됩니다. 마지막에 전체 길이를 비교함으로써 모든 요소가 정확히 한 번씩 사용되었는지도 함께 확인할 수 있습니다.
Python 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(nums, pieces):
temp = []
for p in pieces:
if p[0] not in nums:
return False
l = len(p)
indx = nums.index(p[0])
if nums[indx:indx+l] != p:
return False
else:
temp.extend(p)
if len(nums) == len(temp):
return True
else:
return False
nums = [5,1,12,36,2,47,6]
pieces = [[2,47,6],[12,36],[1],[5]]
print(solve(nums, pieces))입력
[5,1,12,36,2,47,6], [[2,47,6],[12,36],[1],[5]]
출력
True
시간 복잡도 분석
각 조각에 대해 nums.index() 호출은 최악의 경우 O(n) 시간이 걸리고, 슬라이싱 비교 역시 O(n)입니다. 조각의 총 길이의 합은 n을 넘지 않으므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 결과를 저장하는 temp 리스트 때문에 O(n)입니다. 요소가 고유하다는 전제 덕분에 해시 맵 등 추가 자료구조 없이도 간결하게 문제를 해결할 수 있습니다.