[백준BOJ] 18870번 좌표 압축.py

 

백준 저지에서 좌표 압축을 파이썬을 통해 풀어 보았다. 

 

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

18870번: 좌표 압축

18870번 좌표 압축.py

tomy9729/Algorithm

 

 

 

 

18870번 좌표 압축

문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

정렬과 연관된 실버 2 문제이다. 정렬을 사용한다 뿐이지 정렬보다는 set과 hash가 더 중요한 것 같다. 숫자와 숫자의 대소 관계를 통해 어떤 숫자가 몇 번째로 큰지를 구해야 한다. 여기서 숫자 크기만큼 배열을 만들어서 저장할 수도 있겠지만 숫자의 범위가 무려 2*10^9이기 때문에 비효율적이다. 여기서 Hash를 사용하면 되겠다고 생각했다.

 

숫자의 개수는 중요하지 않기 때문에 먼저 중복되는 숫자들을 제거해준다. 파이썬에서는 set을 통해 단 한 줄 만에 배열에서 중복되는 숫자들을 제거할 수 있다. 다음으로 숫자들끼리의 대소 비교를 위해 정렬해준다. sorted()를 통해서 정렬했다.

 

정렬된 숫자에 대해서 각 숫자의 index는 곧 자기보다 작은 숫자의 개수를 의미한다. 만약 index가 0이라면 자기보다 작은 숫자는 없고 index가 3이라면 자기보다 작은 숫자의 개수가 3개임을 뜻한다. 여기서 각 숫자와 index를 매칭 해주기 위해 hash를 사용했다. 파이썬에서는 dictionary라고 한다. dictionary를 통해 각 숫자에 index를 매칭 한다.

 

기존 배열인 nums에 접근하여 dictionary를 통해 각 숫자에 매칭 된 index를 출력한다.

#18870번 좌표 압축
if __name__ == "__main__":
  n = int(input())
  nums = list(map(int,input().split()))
  result = list(sorted(set(nums))) #set을 통해 중복 제거
  dic = {}
  for i in range(len(result)) : 
    dic[result[i]] = i #dictionary를 통해 각 숫자에 매칭되는 출력값 설정
  for i in nums : 
    print(dic[i],end = ' ')