백준 18870번. 좌표 압축 (파이썬)

문제

 

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

18870번: 좌표 압축

 

 

 

 

문제 풀이

 

1. 먼저 배열의 중복을 제거하고 정렬하는 것이 중요하다.

 

여기서 나는 자료형 set은 정렬을 할 수 없다고 생각했다...

그래서 딕셔너리를 사용해 중복을 제거하고, 새로운 리스트에 딕셔너리의 키값을 넣어주었다.

그 후, 새로운 리스트를 정렬해줬다.

 

2. 중복제거한 정렬 리스트에서 해당 숫자의 인덱스를 찾으면 그게 답이다.

 

예를 들어 [1, 2, 3, 4] 라는 리스트가 있을 때, 3보다 작은 숫자의 개수는 2개이다. 3의 인덱스 또한 2이다.

따라서 인덱스를 찾아주는 것이 관건이다.

나는 빠르게 탐색해주기 위해서 시간복잡도 O(logN)인 이분탐색을 사용해서 인덱스를 찾아 주었다.

 

import sys
input=sys.stdin.readline

n=int(input())
arr=list(map(int,input().split()))

#딕셔너리를 사용해 중복제거
arr_dict=dict()
for x in arr:
    arr_dict[x]=1

#중복제거한 리스트 생성 후, 정렬
arr_set=[]
l=0
for key in arr_dict.keys():
    arr_set.append(key)
    l+=1
arr_set.sort()

#이분탐색으로 인덱스 위치 빠르게 탐색
res=[]
for x in arr:
    start=0
    end=l
    while start<=end:
        mid=(start+end)//2
        if arr_set[mid]==x:
            res.append(mid)
            break
        elif arr_set[mid]<x:
            start=mid+1
        else:
            end=mid-1

for x in res:
    print(x,end=' ')

 

 

 

 

더 나은 풀이

 

1. set( ) 함수와 sorted( ) 함수를 사용해 중복제거한 정렬 리스트를 만들어준다.

 

2. 위에서 말했듯이 값의 인덱스를 찾아주는 것이 관건이다.

이 리스트에서 enumerate( )함수를 사용해 인덱스와 값에 동시에 접근하여 {값: 인덱스} 형식의 딕셔너리를 만들어준다.

그러면 딕셔너리의 값만 확인해주면 되기 때문에 O(1)에 답을 찾을 수 있다.

 

import sys
input=sys.stdin.readline

n=int(input())
arr=list(map(int,input().split()))

arr_sort=sorted(set(arr))
arr_dict=dict()
for idx, val in enumerate(arr_sort):
    arr_dict[val]=idx

res=[]
for x in arr:
    res.append(arr_dict[x])

for x in res:
    print(x,end=' ')

 

 

 

 

배운 점

 

1. 자료형 set는 sort( )함수로 정렬을 할 수 없지만, sorted( )함수를 사용하면 정렬할 수 있다.

그리고 sort( )함수는 아무것도 반환하지 않지만 sorted( )함수는 정렬된 새로운 리스트를 반환한다.

 

2. enumerate( )함수는 리스트의 인덱스와 값에 동시에 접근할 수 있다.

 

3. 구글링하다가 알게 된 것이 있는데, for x in arr과 for x in set의 시간 복잡도가 다르다는 것이다.

for x in arr은 O(N)이지만, for x in set은 O(1)이다.

그 이유는 파이썬에서 set은 해시테이블로 저장되기 때문에, 탐색하는데 O(1)으로 끝낸다.

시간 복잡도를 줄이는 데 좋은 팁이라고 생각한다.