[백준/Python] 18870번 - 좌표 압축

 

문제

https://www.acmicpc.net/problem/18870

 

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

풀이

 

input으로 받은 list를 set으로 중복 원소를 제거한 뒤 sorted 함수를 이용해 오름차순으로 정렬해서 dictionary에 순차적으로 저장하면 풀 수 있는 문제다.

아래는 작성한 코드다.

​

 

Code (내장 함수)

 

tc=int(input())
ans_lst=list(map(int,input().split()))
c=list(set(ans_lst)) #set으로 중복을 제거
n=len(c)
st_lst=sorted(c) #sorted를 활용해 오름차순으로 정렬
dic={st_lst[i]:i for i in range(n)} #dic에 저장, 오름차순으로 정렬 되어 있으므로 맨 앞의 숫자는 value가 0 
for j in ans_lst:
    print(f'{dic[j]} ',end='') #출력

 

 

풀이 2 (실패)

 

최근에 알고리즘 문제를 풀 때 최대한 내장함수를 사용하지 말고 풀라고 해서 내장함수 없이 문제를 풀려고 했다. 처음에는 주어진 제한을 보고 어떤 정렬 방법을 사용할까 고민했는데, K가 10^9이고, N은 10^6이라 시간복잡도가 O(N^2)인 정렬보다 counting sort함수를 만들어 사용하는게 나을 것 같았다. 문제는 counting sort함수를 사용해도 K가 N보다 매우 컸기 때문에 메모리 초과를 당했다...

 

Code (메모리 초과...)

 

 

tc=int(input())
ans_lst=list(map(int,input().split()))
c=[]
d=[0]*(2*10**9+1)
for j in ans_lst:
    if j in c:
        pass
    else :
        c.append(j) #c== 원소의 종류는 뭐가 있는지
for k in c:
    d[k+10**9]+=1
for j in range(2*10**9):
    d[j]=d[j+1]
for j in ans_lst:
    print(f'{d[j+10**9]-1} ',end='')

 

---

 

풀이 3 (성공)

 

 

일반적인 정렬로는 시간 복잡도가 O(N^2)가 나왔기 때문에 내장함수는 어떤 시간복잡도를 가진 정렬을 사용하는지 궁금해 졌다. 그래서 sorted() 가 어떤 정렬을 사용하는지 python의 공식 문서를 찾아보고 구글링을 했다.

 

https://leffept.tistory.com/432

 

python의 sort()와, sorted()는 Tim sort라는 정렬 알고리즘으로 삽입정렬과 병합정렬을 합친 알고리즘이라고 한다.

그래서 병합정렬을 하는 함수를 만들고 다시 문제를 풀었다. 문제는 병합정렬을 하기 전에 리스트에서 중복된 원소를 제거 해야하는데, 이 때 또 시간 초과가 발생했다. (중복된 원소를 제거하는 과정에서 시간 복잡도가 다시 O(N^2)이 된 거 같다...)

이를 해결하기 위해 이번에는 python의 내장함수 set()이 어떤 원리로 작동하는지 찾아봤다.

찾아본 결과 set은 해시함수를 이용해 해시 값을 저장하는 해시테이블이라는 자료구조를 사용한다고 한다. 쉽게 말해 값을 해시함수를 이용해 key값으로 변환하고 그 key값에 해당하는 값을 찾는 방식(추후에 더 공부할 예정...)

그래서 처음에는 set()을 사용하지 않고 문제를 풀기 위해 실제로 어떻게 알고리즘이 짜여있는지 알아보려고 했다. 하지만 Python이 C로 만들어진 언어이고 마찬가지로 set()도 C로 코딩되어 있어서 파이썬으로 당장 구현하기는 힘들어 보였다... 그래서 반쯤 포기했는데 마침 dictionary도 해시 테이블로 자료를 찾아 검색이 빠르다고 해서 dictionary를 활용해 중복인 원소를 제거해 줬다. 아래는 sorted()와 len(), set()을 전부 사용하지 않고 작성한 코드다.

 

 

Code (Merge sort, dictionary활용)

 

 

#=========================== 병합정렬하는 함수
def sortfx(lst,num):
    if num<2:
        return lst
    left=int(num/2)
    right=num-left
    l_lst=sortfx(lst[:left],left)
    r_lst=sortfx(lst[left:],right)
    return merg_s(l_lst,r_lst,left,right)
def merg_s(left,right,l_num,r_num):
    n_lst=[]
    l_n=0
    r_n=0
    while l_n<l_num and r_n<r_num:
        if left[l_n]<right[r_n]:
            n_lst.append(left[l_n])
            l_n+=1
        else:
            n_lst.append(right[r_n])
            r_n+=1
    while l_n<l_num:
        n_lst.append(left[l_n])
        l_n+=1
    while r_n<r_num:
        n_lst.append(right[r_n])
        r_n+=1
    return n_lst
#=========================
tc=int(input())
ans_lst=list(map(int,input().split()))
c_di={}
c=[]
dic=dict()
num=0
for j in ans_lst:
    c_di[j]=0 #dic를 활용해중복제거
for j2 in c_di: #중복이 제거된 원소를 c 리스트에 저장 하고 num 변수로 리스트 길이 측정
    c.append(j2)
    num+=1
st_lst=sortfx(c,num)
for i in range(num):
    dic[st_lst[i]]=i
for j in ans_lst:
    print(f'{dic[j]} ',end='')

 

---

 

내장함수를 사용하지 않고 문제를 풀려고 했더니 1문제를 푸는데 2~3시간 정도 걸렸다...ㅠㅠ

 

https://www.acmicpc.net/problem/18870