[알고리즘]백준 1927번: 좌표 압축

알고리즘 유형: 정렬, 자료구조 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

풀이

 

---

정렬과 자료구조가 섞여있는 문제 

중복을 허용하지 않으므로(갯수를 셀때) 기본 자료형 중 중복을 허락하지 않는 집합과 딕셔너리를 떠올렸습니다 

 

처음에는 집합만을 이용해서 해결을 하려고 했습니다

집합을 슬라이싱한 리스트에 대해서 반복하다보니 시간초과가 걸린것 같습니다.

N개의 리스트의 원소를 집합에 삽입하는데  $O(N)$이므로 이를 N번 반복해서

여기서만 최소 $O(N^2)$이 나온거 같습니다  

import sys 
N= sys.stdin.readline().strip()
arr= list(map(int,sys.stdin.readline().strip().split(" ")))

arr_enu =enumerate(arr)
arr_= [0 for i in range(len(arr))]
arr_enu =sorted(arr_enu, key= lambda x: x[1])

for idx, x in enumerate(arr_enu):
    if idx!=0:
        arr_[x[0]] =len(set(arr[:idx])) 
        # print(arr_enu[:idx])
    else: 
        arr_[x[0]]=0
print(arr_)

두번째로 딕셔너리 자료형만을 활용했습니다

 

리스트를 정렬해주고 , 이를 딕셔너리에 넣어줍니다. 넣어주는 과정에서 cnt변수를 통해 

지금까지 원소를 몇개나 봤는지 세어주는데, 중복이 있는 경우 더해주지 않습니다 

 

정렬이 $O(nlogn)$으로 알고 있고, 나머지는 N정도의 복잡도를 가졌을걸로 보입니다 

import sys
from collections import defaultdict  
N= sys.stdin.readline().strip()
arr= list(map(int,sys.stdin.readline().strip().split(" ")))
arr_dict =defaultdict(int)
arr_sort=sorted(arr)
cnt= -1 
for num in arr_sort:
    if num not in arr_dict.keys():
        cnt+=1
        arr_dict[num]=cnt
        
    else: 
        arr_dict[num]=cnt
new_arr =[]
for num in arr: 
    new_arr.append(arr_dict[num])
print(" ".join(map(str, new_arr)))

 

집합과 딕셔너리를 모두 활용하는 경우 코드를 조금 깔끔하게 짤 수 있습니다. 

대신 시간이 더 오래 걸리는 단점이 있습니다

 

import sys
from collections import defaultdict  
N= sys.stdin.readline().strip()

arr = list(map(int, sys.stdin.readline().strip().split(" "))) 
arr_sort = sorted(set(arr)) # list를 순서대로 sort

arr_dict= {arr_sort[i] : i for i in range(len(arr_sort))}
for i in arr:
    print(arr_dict[i], end=' ')

 

추정으로는 정렬에서 시간이 가장 오래걸리는 문제라 시간을 여유롭게 가져가고 싶다면

기본 함수말고 기수정렬 알고리즘을 활용하는게 가장 좋아보입니다.