문제 개요
두 개의 배열 arr1과 arr2가 있다고 가정해 보겠습니다. arr2의 요소들은 모두 고유하며, arr2에 포함된 모든 요소는 arr1에도 존재합니다. 이때 arr1의 요소들을 arr2에서의 등장 순서와 동일하게 재정렬해야 합니다. 만약 arr2에는 없지만 arr1에는 있는 요소들이 있다면, 이 요소들은 배열의 맨 뒤에 오름차순으로 배치해야 합니다.
예를 들어 arr1이 [2,3,1,3,2,4,6,7,9,2,19]이고, arr2가 [2,1,4,3,9,6]이라면 결과는 [2,2,2,1,4,3,3,9,6,7,19]가 됩니다. arr2에 속한 숫자들은 arr2의 순서대로 배치되고, 나머지 숫자들(7, 19)은 마지막에 오름차순으로 정렬된 것을 확인할 수 있습니다.
해결 접근 방법
이 문제는 해시맵(딕셔너리)을 활용한 빈도수 계산으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- arr1에 있는 각 요소의 빈도수를 저장할 맵(딕셔너리) D를 생성합니다.
- 결과를 담을 배열 res와 임시 배열 temp를 정의합니다.
- arr2의 각 요소 i에 대해 다음을 반복합니다.
- j를 0부터 D[i]-1까지 반복하면서 i를 res에 추가합니다.
- 처리가 끝나면 D[i]를 0으로 설정하여 중복 처리를 방지합니다.
- D의 모든 (키, 값) 쌍을 순회하며, 값이 0이 아닌 경우 해당 키를 값의 횟수만큼 temp에 추가합니다.
- temp를 오름차순으로 정렬한 뒤 res의 끝에 붙이고, 최종 결과인 res를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 이해해 보겠습니다.
class Solution(object):
def relativeSortArray(self, arr1, arr2):
# arr1의 요소별 빈도수 계산
d = {}
for i in arr1:
if i not in d:
d[i] = 1
else:
d[i] += 1
res = []
temp = []
# arr2 순서대로 요소 배치
for i in arr2:
for j in range(d[i]):
res.append(i)
d[i] = 0
# arr2에 없는 요소는 임시 배열에 저장
for k, v in d.items():
if v:
for i in range(v):
temp.append(k)
# 오름차순 정렬 후 결과에 추가
temp.sort()
res.extend(temp)
return res
ob1 = Solution()
print(ob1.relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]))입력
[2,3,1,3,2,4,6,7,9,2,19] [2,1,4,3,9,6]
출력
[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
복잡도 분석
이 알고리즘의 시간 복잡도는 arr1의 길이를 n, arr2의 길이를 m이라 할 때 O(n + m + k log k)입니다. 여기서 k는 arr2에 없는 고유 요소의 개수로, temp 배열을 정렬하는 데 드는 비용입니다. 공간 복잡도는 빈도수 맵과 결과 배열을 위해 O(n)입니다. 해시맵 덕분에 각 요소의 위치를 빠르게 찾을 수 있어 전체적으로 매우 효율적인 방식입니다.