[python] 백준 18870번 - 좌표압축 (시간초과 문제)

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

 

문제 자체는 어렵지 않았다.

입력받은 리스트에서 중복을 제거하기 위해 set()을 사용한 후 다시 리스트로 변환하고

이를 정렬하여 정렬된 수의 인덱스 값이 곧 그 수의 좌표 압축한 결과가 된다.

시간 초과가 계속 떠서 알아본 결과

처음 인덱스 값을 구하기 위해 index()를 사용하였는데 시간복잡도가 O(n)이기 때문에 시간초과가 발생했다.

그래서 이를 해결하기 위해 dictionary를 사용하여 key값을 이용해 바로 검색할 수 있게 하였다.

 

import sys

n =int(sys.stdin.readline())
lst = list(map(int, input().split())) 
    
def split(data):
    if len(data) <=1:
        return data
    medium = int(len(data)/2)
    left = split(data[:medium])
    right= split(data[medium:])
    return merge(left,right)

def merge(left,right):
    merged=[]
    l_point,r_point = 0,0
    
    while len(left)>l_point and len(right)>r_point:
        if left[l_point] > right[r_point]:
            merged.append(right[r_point])
            r_point+=1
        else:
            merged.append(left[l_point])
            l_point+=1
    
    while len(left)>l_point:
        merged.append(left[l_point])
        l_point+=1
    
    while len(right)>r_point:
        merged.append(right[r_point])
        r_point+=1
    
    return merged

sorted_list = split(list(set(lst)))
dic ={sorted_list[i]:i for i in range(len(sorted_list))}
for i in lst:
    print(dic[i], end=' ')