수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- -109 ≤ Xi ≤ 109
예제 입력 2
6
1000 999 1000 999 1000 999
풀이 방식
문제를 보고 가장 먼저 떠오르는 방식은 2중 for문으로 푸는 O(N^2) 풀이 방식이다. 하지만 제한을 보면 알겠지만 N의 범위가 1,000,000이기 때문에 O(N^2)의 풀이는 시간초과가 뜰 것이다.
1번 풀이: 시간초과
그래도 일단 O(N^2) 풀이로 풀어본 방식이고 역시나 시간초과가 발생하였다..
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
answer = []
for i in range(len(arr)):
count = 0
for j in range(len(arr)):
if i == j: continue
if arr[i] > arr[j]: count += 1
answer.append(count)
print(*answer)
2번 풀이: 성공
bisect 모듈을 활용하여 for문을 돌면서 각 원소가 들어갈 위치(index)를 answer 리스트에 append 해 주는 식으로 구현을 했다.
하지만 중복이 있으면 들어갈 index가 뒤로 밀려버리기 때문에 set을 하나 정의해서 해당 set에서 bisect 인덱스를 찾는 코드를 구현했다.
import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
tmp = []
for i, v in enumerate(arr):
tmp.append([i, v])
arr.sort()
arr_set = list(set(arr))
tmp.sort(key=lambda x: x[1])
arr_set.sort()
answer = [0] * N
for i in range(len(arr)):
idx = bisect_left(arr_set, arr[i])
answer[tmp[i][0]] = idx
print(*answer)
다른 풀이
내가 푼 풀이와 유사하지만 쓸모 없는 부분을 최대한 줄여서 푼 방식이다.
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
print(dic[i], end = ' ')
set 집합을 정렬한 리스트를 하나 정의 하는 것까지는 똑같은데 딕셔너리를 활용하면 쉽게 구현이 가능하다.
딕셔너리의 key값이 set 리스트의 원소이고 value가 리스트의 길이 range iterable 객체로 하면 각 key에 대해 위치를 저장할 수 있게되므로 arr에 대해 for문을 하나씩 돌면서 딕셔너리에서 각 원소를 key로 하는 value를 출력하면 된다.
