[BOJ #18870] 좌표 압축

문제

수직선 위에 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 (시간 초과)

from sys import stdin; input = stdin.readline
N = int(input())
arr = list(map(int, input().split()))
set_arr = list(set(arr))
for num in arr:
    cnt = 0
    for snum in set_arr:
        if snum < num:
            cnt += 1
    print(cnt, end=' ')

이건 내가 처음 푼 코드!! 시간 초과 났는데 도저히 시간 복잡도를 줄일 방도가 생각이 나지 않아... 서치의 힘을 빌려보았당..

 

내가 쓴 코드 2 (시간 초과)

from sys import stdin; input = stdin.readline
N = int(input())
arr = list(map(int, input().split()))
set_arr = sorted(list(set(arr)))
for num in arr:
    print(set_arr.index(num), end=' ')

찾아봤는데 다들 index로 써서 틀렸다는거다.. 나는 엥 이게 머지? 내가 문제를 잘못 알고있나?? 했다... 생각해보니 인덱스로 풀면 간단히 풀리는 문제긴 했다.. 전혀 생각지도 못한 방법이어서 시간초과 나는 코드이지만, 한 번 코드로 써봤당.

 

내가 쓴 코드 3

from sys import stdin; input = stdin.readline
N = int(input())
arr = list(map(int, input().split()))
set_arr = sorted(list(set(arr)))
index_dic = {set_arr[i]:i for i in range(len(set_arr))}
for num in arr:
    print(index_dic[num], end=' ')

이 문제는 딕셔너리를 풀어야 풀리는 문제였다.. 인덱스를 어떻게 딕셔너리로..? 사실 할 수 있을 것 같긴 했는데,, 딕셔너리에 저렇게 for문을 쓸 수 있다는 생각을 못했다. ㅎㅎ 코드 4개 중에 가장 시간, 메모리 측면에서 효율적인 코드!가 되겠다 !!

 

내가 쓴 코드 4

from sys import stdin; input = stdin.readline
N = int(input())
arr = list(map(int, input().split()))
set_arr = sorted(list(set(arr)))
index_dic = dict(zip(set_arr, list(range(len(set_arr)))))
for num in arr:
    print(index_dic[num], end=' ')

사실 3번째 코드가 끝이었는데,, 태그 입력하다가 값 압축 이 있어서 으엥 이거 원래 zip 써서 푸는 게 정석인가? 싶어서 zip을 활용한 풀이를 찾아봤다. 하지만 zip은 너무 생소해....

 

zip() 함수로 dictionary 구현하기 !
-> dict(zip(리스트1, 리스트2)) -> {리스트1의 요소 : 리스트2의 요소, ...}

 

제출결과

아자아자 아좌좌좌!!!