boj-18870(좌표 압축)

좌표 압축 문제이다.
좌표 압축이라는 개념이 생소했는데, 문제를 읽으면서 이해해보았다.
주어진 좌표가
2 -1 3 9 4
이런식이라면, 자신의 좌표보다 서로 다른 작은 값의 갯수가 대응되는 형태인 것 같았다.
즉

2	-1	3	9	4
1	0	2	4	3

이렇게 되는 것인데, 문제는 '서로 다른' 이라는 것이었다.
예시에도 나와있는데,

1000	999	1000	999
1	0	1	0

이 것의 대응형태는 이렇다.
1000과는 서로 다른 작은 수의 갯수는 999 1개밖에 없기 때문이다.

접근

---

일단 같은 원소에 대해서는 같은 값이 나온다는 걸로 봐서, 딕셔너리 형태로 접근을 해보았다.
처음에 생각나는대로 접근을 해보았을 때 방식은, dict 에 key를 입력받은 숫자로, value를 0으로 초기화해주었다.
그리고 원소마다의 대소를 비교하여 value를 하나씩 늘려줬다.

import sys
input = sys.stdin.readline
N = int(input())
num_list = list(map(int, input().split(" ")))
num_dic = {item:0 for item in num_list}

for i in num_dic.items():
    for j in num_dic.items():
        if i[0] > j[0]:
            num_dic[i[0]] += 1
    
for i in range(N):
    sys.stdout.write(str(num_dic[num_list[i]]))
    sys.stdout.write(' ')

이 것의 문제는 이중 for에 의한 복잡도가 너무 커진다는 것이다... 그래서 역시 시간초과가 뜬다

해결책 생각

---

같은 원소에 대해서는 중복을 허용하지 않고, 없애주는 방법에는 dict형과 set형태가 있다.
dict형으로 하나하나 직접 찾아서 count해주는거는 너무 복잡하니까, 간단하게 생각해보았더니
'그냥 중복 원소를 제거하고, 정렬해버리면 그 index가 결국 자신보다 더 작은 애들의 갯수 아닐까?'
라고 생각했다.
즉, 이러한 케이스를

2	-1	3	9	4
1	0	2	4	3

정렬하면,
-1 2 3 4 9 가 되고 index를 부여하면

	-1	2	3	4	9
$i$	0	1	2	3	4

결국 인덱스가 자신보다 작은 애들의 갯수라고 생각할 수 있게 되는게 맞다!
그래서 index랑 숫자를 매칭해주면, 쉽게 끝나는 것이라고 생각하게 되었다.

import sys
input = sys.stdin.readline
N = int(input())
num_list = list(map(int, input().split(" "))) # list로 숫자를 입력받고
set_num = list(sorted(set(num_list))) # set형으로 변환하여, 중복을 제거한 뒤, sort하고 다시 list로 변환
num_dic = {}

for i in range(len(set_num)):
    num_dic[set_num[i]] = i # dict에 해당하는 숫자를 key로 value를 index로 부여
    
for i in range(N):
    sys.stdout.write(str(num_dic[num_list[i]]) + ' ') # 출력 !

맞았습니다!