https://codeforces.com/contest/1497/problem/A
시간 초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- n (1 ≤ n ≤ 100)
- a1, a2, ..., an(1 ≤ ai ≤ 100)
output :
- For each test case print an array b1, b2, ..., bn — the optimal reordering of a1, a2, ..., an, so the sum of MEX on its prefixes is maximized.
각 테스트케이스에서 배열 b를 출력하시오. a 배열의 순서를 재배치하여 MEX의 합을 가장 크게 하는 배열 b를 만드시오.
조건 :
-
You are given an integer n and an array a1, a2, ..., an. You should reorder the elements of the array a in such way that the sum of MEX on prefixes (i-th prefix is a1, a2, ..., ai) is maximized.
n과 a 배열을 입력받습니다. 배열 a의 원소를 재배치하여 MEX의 합을 최대화합니다. -
MEX of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set.
MEX는 음이 아닌 정수를 나타내는데 이는 이미 만들어진 배열에 속하지 않는 가장 작은 수를 의미합니다.
합을 가장 크게 하려면 결국 가장 작은 수부터 새롭게 재배치해야한다.
그리고 재배치를 할 때 이미 들어갔던 수를 다시 넣는 것은 동일한 값을 반복시키는 것 밖에 되지 않는다.
그렇기때문에 마지막에 모든 정렬이 끝난 후 맨 뒤에 추가해준다.
입력받은 배열을 정렬한 후에 이 값이 나온적이 있다면 temp배열에 넣어 마지막에 추가해주고 그렇지 않다면 ans배열에 넣어준다.
합을 구하라는 것이 아니기때문에 배열만 해주면 된다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
num, ans, temp = [0] * 101, [], []
data.sort()
for item in data:
if num[item] == 0:
ans.append(item)
num[item] += 1
else:
temp.append(item)
ans += temp
for item in ans:
print(item, end=" ")
print()
