알고리즘 - Python / 백준 - 18870번 : 좌표 압축

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

18870번: 좌표 압축

 

---

풀이

• 문제 내용은 받아온 수들을 정렬해 순서를 정해주는 문제 였다.
• 중복되는 수의 경우 같은 순서에 위치 하게 된다.
• 힙 구조를 이용한 힙 정렬을 이용해 정렬하고 , 이전에 pop 된 수와 비교하여 같으면 index를 증가시키지 않도록 구현했다.

 

import sys
import heapq

n = int(sys.stdin.readline())
heap = []
stack= list(map(int,sys.stdin.readline().split()))
for i in range(0,n):
  heapq.heappush(heap, (stack[i],i))

cnt = 0
last_num = 0

for i in range(0,n):
  if i == 0:
    pops = heapq.heappop(heap)
    last_num = pops[0]
    stack[pops[1]] = cnt
  else:
    pops = heapq.heappop(heap)
    if last_num == pops[0]:
      stack[pops[1]] = cnt
    else:
      cnt += 1
      last_num = pops[0]
      stack[pops[1]] = cnt

for i in range(0,n-1):
  print(stack[i],end=" ")
print(stack[n-1])

---