문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9
예제 입력 1
5
2 4 -10 4 -9
예제 출력 1
2 3 0 3 1
예제 입력 2
6
1000 999 1000 999 1000 999
예제 출력 2
1 0 1 0 1 0
문제 해결 과정
해당 문제에서 숫자가 여러 개 주어졌을 때, 리스트 내의 숫자들 중 인덱스의 숫자보다 작은 것의 개수를 찾으면 된다.
처음에는 이중 포문을 사용해서 문제 해결을 시도했다.
입력 받은 숫자들을 하나에는 리스트로 담아두고, 하나는 오름차순으로 정렬한 후 집합에 담는다. 정렬을 미리 하는 이유는 조금이라도 시간을 줄이기 위해서 그렇게 했다. 그리고 집합에 담으면 중복값이 제거 되기 때문에 집합에 담았다.
N = int(input())
xy = list(map(int,input().split()))
xy_sort = sorted(xy)
xy_set = set(xy_sort)
print(xy_set)
result = []
cnt = 0
for i in xy :
for j in xy_set :
if i > j : cnt+=1
result.append(cnt)
cnt = 0
print(*result)하지만 N의 최대치인 1,000,000까지 가면 시간초과가 난다.
그러면 다른 자료 구조를 써야된다는 의미인데, 당시에는 어떤 자료 구조를 써야할지 생각이 나지 않았다.
결국 고민 끝에 다른 블로그를 참고하여 문제를 해결했다.
정렬을 해서 집합에 넣는 거까지는 똑같다.
그리고 해당 숫자와 인덱스를 딕셔너리에 넣으면 인덱스가 자신보다 작은 숫자를 표시하는 것이나 다름 없었다.
최종 코드
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 = ' ')참고 블로그
