좌표 압축

알고리즘 구분 : 정렬, 좌표 압축

최초 문제 풀이 : xi를 좌표 압축한 결과, x'i의 값은 xi > xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다는 부분을 구현하는 부분이 핵심이였습니다. 이를 구현하기 위해선 중복된 값을 제거한 뒤 정렬을 하여야 합니다. 그렇기에, 파이썬에서 중복제거 기능이 있는 set() 메서드를 통해서 중복 제거를 한 뒤에, sorted() 메서드를 통해서 정렬할 수 있도록 구현하였습니다. 이 후, 해당 값들을 리스트 자료형으로 변환한 뒤에, 인덱스 값을 출력하도록 소스 코드를 구현하였으나 시간 초과가 나왔습니다.

최초 소스 코드 :

n = int(input())

data = list(map(int, input().split()))

temp = list(sorted(set(data)))
for i in range(len(data)):
    print(temp.index(data[i]), end = " ")

위의 코드에서 시간 초과가 발생하게 된 코드는 temp.index(data[i])입니다. index() 메서드는 시간복잡도가 O(N)인 반면, 딕셔너리 형의 value 값 호출의 경우는 O(1)로 상수의 시간 복잡도를 가지고 있습니다. 최초 소스 코드는 O(N^2)의 시간복잡도를 가지고 있으며, 정답 소스 코드는 O(N)의 시간 복잡도를 가지고 있는 것입니다.

정답 소스 코드 :

n = int(input())

data = list(map(int, input().split()))

temp = list(sorted(set(data)))
temp = {temp[i]:i for i in range(len(temp))}
for i in data:
    print(temp[i], end = " ")

• 문제 출처 : https://www.acmicpc.net/problem/18870
• 해당 정답 소스 코드는 백준에서 "맞았습니다!!" 판정을 받았습니다.